oj.uz

Submission #872584

# Submission time Handle Problem Language Result Execution time Memory
872584 2023-11-13T11:51:27 Z Yahia_Emara Kamenčići (COCI21_kamencici) C++17
70 / 70
 33 ms 62416 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ctoi(x) int(x-'0')
#define cdv(x,y) (((x)+(y)-1)/(y))
#define LOOP(n) for(int rp=0;rp<(n);rp++)
#define sz(x) int(x.size())
#define dbg(x) cout << (#x) << " : " << x << endl;
#define sq(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef long double dl;
const int SZ=2e5+7;
bool dp[350][350][350],vs[350][350][350];
int n,k,p[350],a[350]{};
bool solve(int l,int r,int c){
    if(c==k)return 0;
    int C=(l>0?p[l-1]:0)+p[n-1]-p[r];
    if(C-c==k)return 1;
    if(vs[l][r][c])return dp[l][r][c];
    vs[l][r][c]=1;
    return dp[l][r][c]=!(solve(l+1,r,C-c)&solve(l,r-1,C-c));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tt=1;
    //cin >> tt;
    LOOP(tt){
        cin >> n >> k;
        for(int i=0;i<n;i++){
            char c;cin >> c;
            p[i]=(i>0?p[i-1]:0);
            if(c=='C')p[i]++,a[i]=1;
        }
        cout << (solve(0,n-1,0)?"DA":"NE");
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4560 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4560 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 7016 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4560 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 7016 KB Output is correct
13 Correct 2 ms 9308 KB Output is correct
14 Correct 29 ms 62036 KB Output is correct
15 Correct 8 ms 29784 KB Output is correct
16 Correct 33 ms 48480 KB Output is correct
17 Correct 26 ms 62416 KB Output is correct
18 Correct 12 ms 35676 KB Output is correct