oj.uz

Submission #494203

# Submission time Handle Problem Language Result Execution time Memory
494203 2021-12-14T18:50:42 Z AlperenT Kamenčići (COCI21_kamencici) C++17
0 / 70
 1 ms 588 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 350 + 5, INF = 1e9 + 5;

int n, k;

char arr[N], wina[N][N], winb[N][N];

pair<int, int> a[N][N], b[N][N];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            wina[i][j] = winb[i][j] = 'D';
        }
    }

    cin >> n >> k;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    for(int i = 1; i <= n; i++){
        if(arr[i] == 'C') a[i][i] = {1, 0}, b[i][i] = {0, 1};

        if(k == 1) wina[i][i] = 'L', winb[i][i] = 'L';
    }

    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;

            if(winb[l + 1][r] == 'L' || winb[l][r - 1] == 'L') wina[l][r] = 'W';
            if(winb[l + 1][r] == 'W' && winb[l][r - 1] == 'W') wina[l][r] = 'L';

            a[l][r] = {b[l + 1][r].first + (arr[l] == 'C'), b[l + 1][r].second};

            if(b[l][r - 1].first + (arr[r] == 'C') < a[l][r].first) a[l][r] = {b[l][r - 1].first + (arr[r] == 'C'), b[l][r - 1].second};

            if(wina[l][r] == 'D'){
                if(a[l][r].first >= k) wina[l][r] = 'L';
                else if(a[l][r].second >= k) wina[l][r] = 'W';
            }

            if(wina[l + 1][r] == 'L' || wina[l][r - 1] == 'L') winb[l][r] = 'W';
            if(wina[l + 1][r] == 'W' && wina[l][r - 1] == 'W') winb[l][r] = 'L';

            b[l][r] = {a[l + 1][r].first, a[l + 1][r].second + (arr[l] == 'C')};

            if(a[l][r - 1].second + (arr[r] == 'C') < b[l][r].second) b[l][r] = {a[l][r - 1].first, a[l][r - 1].second + (arr[r] == 'C')};

            if(winb[l][r] == 'D'){
                if(b[l][r].first >= k) winb[l][r] = 'W';
                else if(b[l][r].second >= k) winb[l][r] = 'L';
            }
        }
    }

    cout << (wina[1][n] == 'W' ? "DA" : "NE");
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -