oj.uz

Submission #486983

# Submission time Handle Problem Language Result Execution time Memory
486983 2021-11-13T17:20:43 Z model_code Kamenčići (COCI21_kamencici) C++17
70 / 70
 188 ms 170968 KB 
#include <cstdio>


using namespace std;

const int MAXN = 352;

int n,k;
char str[MAXN];
int prefix[MAXN];
int dp[MAXN][MAXN][MAXN];

int can_win(int l, int r, int uk){
    int& res = dp[l][r][uk];
    if(res == -1){
        int total_red = prefix[n-1];
        int red_left = prefix[r];
        if(l) red_left -= prefix[l-1];
        int other_red = total_red - red_left - uk;
        if(uk>=k){
            res = 0;
        }else if(other_red>=k){
            res = 1;
        }else{
            if(!can_win(l+1, r, other_red) || !can_win(l, r-1, other_red)){
                res = 1;
            }else{
                res = 0;
            }
        }
    }
    return res;
}

int main(){
    for(int i=0;i<MAXN;i++) for(int j=0;j<MAXN;j++) for(int k=0;k<MAXN;k++)
        dp[i][j][k] = -1;
    scanf("%d%d", &n, &k);
    scanf("%s", str);
    prefix[0] = (str[0] == 'C');
    for(int i=1;i<n;i++) prefix[i] = prefix[i-1] + (str[i] == 'C');

    if(can_win(0, n-1, 0)){
        puts("DA");
    }else{
        puts("NE");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%s", str);
      |     ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 170900 KB Output is correct
2 Correct 119 ms 170888 KB Output is correct
3 Correct 74 ms 170948 KB Output is correct
4 Correct 66 ms 170948 KB Output is correct
5 Correct 68 ms 170912 KB Output is correct
6 Correct 73 ms 170860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 170900 KB Output is correct
2 Correct 119 ms 170888 KB Output is correct
3 Correct 74 ms 170948 KB Output is correct
4 Correct 66 ms 170948 KB Output is correct
5 Correct 68 ms 170912 KB Output is correct
6 Correct 73 ms 170860 KB Output is correct
7 Correct 70 ms 170868 KB Output is correct
8 Correct 71 ms 170884 KB Output is correct
9 Correct 68 ms 170904 KB Output is correct
10 Correct 70 ms 170832 KB Output is correct
11 Correct 72 ms 170948 KB Output is correct
12 Correct 69 ms 170920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 170900 KB Output is correct
2 Correct 119 ms 170888 KB Output is correct
3 Correct 74 ms 170948 KB Output is correct
4 Correct 66 ms 170948 KB Output is correct
5 Correct 68 ms 170912 KB Output is correct
6 Correct 73 ms 170860 KB Output is correct
7 Correct 70 ms 170868 KB Output is correct
8 Correct 71 ms 170884 KB Output is correct
9 Correct 68 ms 170904 KB Output is correct
10 Correct 70 ms 170832 KB Output is correct
11 Correct 72 ms 170948 KB Output is correct
12 Correct 69 ms 170920 KB Output is correct
13 Correct 69 ms 170956 KB Output is correct
14 Correct 97 ms 170952 KB Output is correct
15 Correct 69 ms 170884 KB Output is correct
16 Correct 76 ms 170968 KB Output is correct
17 Correct 72 ms 170956 KB Output is correct
18 Correct 69 ms 170916 KB Output is correct