Submission #494203

#	Time	Username	Problem	Language	Result	Execution time	Memory
494203		AlperenT	Kamenčići (COCI21_kamencici)	C++17	0 / 70	1 ms	588 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40