oj.uz

Submission #874563

# Submission time Handle Problem Language Result Execution time Memory
874563 2023-11-17T09:39:49 Z ngjabach Kamenčići (COCI21_kamencici) C++14
70 / 70
 37 ms 171132 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 29 ms 171088 KB Output is correct
2 Correct 28 ms 171084 KB Output is correct
3 Correct 29 ms 171092 KB Output is correct
4 Correct 28 ms 171084 KB Output is correct
5 Correct 28 ms 171096 KB Output is correct
6 Correct 28 ms 170916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 171088 KB Output is correct
2 Correct 28 ms 171084 KB Output is correct
3 Correct 29 ms 171092 KB Output is correct
4 Correct 28 ms 171084 KB Output is correct
5 Correct 28 ms 171096 KB Output is correct
6 Correct 28 ms 170916 KB Output is correct
7 Correct 28 ms 171088 KB Output is correct
8 Correct 29 ms 171092 KB Output is correct
9 Correct 33 ms 171084 KB Output is correct
10 Correct 28 ms 171100 KB Output is correct
11 Correct 28 ms 171100 KB Output is correct
12 Correct 29 ms 171036 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 171088 KB Output is correct
2 Correct 28 ms 171084 KB Output is correct
3 Correct 29 ms 171092 KB Output is correct
4 Correct 28 ms 171084 KB Output is correct
5 Correct 28 ms 171096 KB Output is correct
6 Correct 28 ms 170916 KB Output is correct
7 Correct 28 ms 171088 KB Output is correct
8 Correct 29 ms 171092 KB Output is correct
9 Correct 33 ms 171084 KB Output is correct
10 Correct 28 ms 171100 KB Output is correct
11 Correct 28 ms 171100 KB Output is correct
12 Correct 29 ms 171036 KB Output is correct
13 Correct 28 ms 170916 KB Output is correct
14 Correct 37 ms 171096 KB Output is correct
15 Correct 30 ms 170972 KB Output is correct
16 Correct 37 ms 171132 KB Output is correct
17 Correct 33 ms 171064 KB Output is correct
18 Correct 30 ms 171108 KB Output is correct