Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //typedef long long ll;
- typedef pair<int, int> ii;
- const int MOD = 1e9+7;
- const int MAX = 5e3 + 10;
- int dp[MAX][MAX], last_w[MAX], last_l[MAX], tw[MAX], tl[MAX];
- bool goat[MAX];
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- #define endl '\n'
- #endif // LOCAL
- int n, m, k; cin >> n >> m >> k;
- for(int i = 0; i < n; i++)
- cin >> goat[i];
- memset(dp, -1, sizeof dp);
- for(int i = 0; i < n; i++) {
- dp[i][m-1] = 0;
- last_l[i] = last_w[i] = INT_MAX;
- if(dp[i][m-1] == 0) last_l[i] = m-1;
- else last_w[i] = m-1;
- }
- for(int j = m-2; j >= 0; j--) {
- memcpy(tl, last_l, sizeof last_l);
- memcpy(tw, last_w, sizeof last_w);
- for(int i = 0; i < n; i++) {
- int nxt = (i+1)%n;
- if(goat[nxt] == goat[i]) { /// I can win if find some winner
- if(j + k >= last_w[nxt])
- dp[i][j] = 1;
- else
- dp[i][j] = 0;
- } else { /// I can win if find some looser
- if(j + k >= last_l[nxt])
- dp[i][j] = 1;
- else
- dp[i][j] = 0;
- }
- if(dp[i][j] == 0) tl[i] = j;
- else tw[i] = j;
- }
- memcpy(last_l, tl, sizeof last_l);
- memcpy(last_w, tw, sizeof last_w);
- }
- for(int i = 0; i < n; i++) {
- if(i) cout << " ";
- if(dp[i][0] == 1) cout << goat[i];
- else cout << !goat[i];
- }
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement