oj.uz

Submission #720650

# Submission time Handle Problem Language Result Execution time Memory
720650 2023-04-08T19:26:03 Z tarushii Kamenčići (COCI21_kamencici) C++14
70 / 70
 134 ms 182924 KB 
#include <bits/stdc++.h>
#define MAXN 360
#define INF 400000

using namespace std;

int N, K;
int arr[MAXN];
int pref[MAXN];
int dp[MAXN][MAXN][MAXN];

int solve(int l, int r, int k){ 
    // min amount of red needed to be taken to force opponent to take k red
    // it is always your turn 
    // inf if impossible 
    // -1 if not computed
    assert(r >= l);
    if (dp[l][r][k]!=-1) return dp[l][r][k];
    else if (k == 0) {
        dp[l][r][k] = 0;
        return 0;
    }
    // if (pref[r] - pref[l-1] == 0) { // all blue 
    //     dp[l][r][k] = (k==0) ? 0 : INF;
    //     return dp[l][r][k];
    // }
    // if (pref[r] - pref[l-1] == r-l+1){ // all red 
    //     dp[l][r][k] = (r-l+1 >= 2*k) ? k : INF;
    //     return dp[l][r][k];
    // }
    else if (r-l+1 < 3){
        if (k > 1) dp[l][r][k] = INF;
        if (k == 1 && (arr[l]||arr[r])) dp[l][r][k] = arr[l]&&arr[r];
        return dp[l][r][k];
    }
    else {
        int leftMove = arr[l] + max(solve(l+2, r, k - arr[l+1]), solve(l+1, r-1, k - arr[r])); // had to take one from the left. 
        int rightMove = arr[r] + max(solve(l+1, r-1, k - arr[l]), solve(l, r-2, k - arr[r-1]));
        dp[l][r][k] = min(leftMove, rightMove);
        return dp[l][r][k];
    }
    // 'cccp'
}

int main(){
     cin >> N >> K;
     for (int i = 1; i <= N; i++){
        char c; cin >> c;
        arr[i] = (c == 'C');
        pref[i] = pref[i-1] + arr[i]; // count number of red balls in range 1..i
     }
     memset(dp, -1, 4*MAXN*MAXN*MAXN);
     int cost = solve(1, N, K);
     if (cost < K) cout << "DA";
     else cout << "NE";
     cout << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 182768 KB Output is correct
2 Correct 82 ms 182800 KB Output is correct
3 Correct 92 ms 182884 KB Output is correct
4 Correct 89 ms 182924 KB Output is correct
5 Correct 73 ms 182800 KB Output is correct
6 Correct 77 ms 182784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 182768 KB Output is correct
2 Correct 82 ms 182800 KB Output is correct
3 Correct 92 ms 182884 KB Output is correct
4 Correct 89 ms 182924 KB Output is correct
5 Correct 73 ms 182800 KB Output is correct
6 Correct 77 ms 182784 KB Output is correct
7 Correct 73 ms 182876 KB Output is correct
8 Correct 84 ms 182776 KB Output is correct
9 Correct 89 ms 182832 KB Output is correct
10 Correct 87 ms 182868 KB Output is correct
11 Correct 76 ms 182856 KB Output is correct
12 Correct 81 ms 182860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 182768 KB Output is correct
2 Correct 82 ms 182800 KB Output is correct
3 Correct 92 ms 182884 KB Output is correct
4 Correct 89 ms 182924 KB Output is correct
5 Correct 73 ms 182800 KB Output is correct
6 Correct 77 ms 182784 KB Output is correct
7 Correct 73 ms 182876 KB Output is correct
8 Correct 84 ms 182776 KB Output is correct
9 Correct 89 ms 182832 KB Output is correct
10 Correct 87 ms 182868 KB Output is correct
11 Correct 76 ms 182856 KB Output is correct
12 Correct 81 ms 182860 KB Output is correct
13 Correct 71 ms 182828 KB Output is correct
14 Correct 115 ms 182860 KB Output is correct
15 Correct 134 ms 182800 KB Output is correct
16 Correct 110 ms 182848 KB Output is correct
17 Correct 86 ms 182888 KB Output is correct
18 Correct 99 ms 182780 KB Output is correct