oj.uz

Submission #656220

# Submission time Handle Problem Language Result Execution time Memory
656220 2022-11-06T14:47:12 Z Hydroxic_Acid Kamenčići (COCI21_kamencici) C++17
70 / 70
 81 ms 175460 KB 
#include <iostream>
#include <cstring>
using namespace std;

int N, K;
int seq[355];
int prefleft[355];
int prefright[355];
int dptable[355][355][355];

bool dp(int i, int j, int k){
    if(k == 0){
        return dptable[i][j][k] = 0;
    }
    if(dptable[i][j][k] != -1){
        return dptable[i][j][k];
    }
    if((prefleft[i] + prefright[j] - seq[i] - seq[j] - K + k) >= K){
        return dptable[i][j][k] = 1;
    }

    if((i + N - j + 1) % 2 == 0){
        dptable[i][j][k] = dp(i + 1, j, k - seq[i]) || dp(i, j - 1, k - seq[j]);
    } else {
        dptable[i][j][k] = dp(i + 1, j, k) && dp(i, j - 1, k);
    }
    return dptable[i][j][k];
}

int main(){
    cin >> N >> K;
    
    for(int i = 0; i < N; i++){
        char c; cin >> c;
        if(c == '\n') cin >> c;
        if(c == 'C') seq[i] = 1;
        else seq[i] = 0;
    }

    prefleft[0] = seq[0];
    for(int i = 1; i < N; i++){
        prefleft[i] = seq[i] + prefleft[i - 1];
    }

    prefright[N - 1] = seq[N - 1];
    for(int i = N - 2; i >= 0; i--){
        prefright[i] = seq[i] + prefright[i + 1];
    }

    memset(dptable, -1, sizeof(dptable));

    if(dp(0, N - 1, K)) cout << "DA";
    else cout << "NE";
}

Compilation message

Main.cpp: In function 'bool dp(int, int, int)':
Main.cpp:13:33: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   13 |         return dptable[i][j][k] = 0;
      |                ~~~~~~~~~~~~~~~~~^~~
Main.cpp:19:33: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   19 |         return dptable[i][j][k] = 1;
      |                ~~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 175308 KB Output is correct
2 Correct 74 ms 175368 KB Output is correct
3 Correct 68 ms 175336 KB Output is correct
4 Correct 63 ms 175364 KB Output is correct
5 Correct 65 ms 175292 KB Output is correct
6 Correct 69 ms 175304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 175308 KB Output is correct
2 Correct 74 ms 175368 KB Output is correct
3 Correct 68 ms 175336 KB Output is correct
4 Correct 63 ms 175364 KB Output is correct
5 Correct 65 ms 175292 KB Output is correct
6 Correct 69 ms 175304 KB Output is correct
7 Correct 72 ms 175372 KB Output is correct
8 Correct 76 ms 175324 KB Output is correct
9 Correct 68 ms 175276 KB Output is correct
10 Correct 70 ms 175288 KB Output is correct
11 Correct 66 ms 175368 KB Output is correct
12 Correct 69 ms 175348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 175308 KB Output is correct
2 Correct 74 ms 175368 KB Output is correct
3 Correct 68 ms 175336 KB Output is correct
4 Correct 63 ms 175364 KB Output is correct
5 Correct 65 ms 175292 KB Output is correct
6 Correct 69 ms 175304 KB Output is correct
7 Correct 72 ms 175372 KB Output is correct
8 Correct 76 ms 175324 KB Output is correct
9 Correct 68 ms 175276 KB Output is correct
10 Correct 70 ms 175288 KB Output is correct
11 Correct 66 ms 175368 KB Output is correct
12 Correct 69 ms 175348 KB Output is correct
13 Correct 65 ms 175272 KB Output is correct
14 Correct 81 ms 175296 KB Output is correct
15 Correct 75 ms 175288 KB Output is correct
16 Correct 77 ms 175392 KB Output is correct
17 Correct 70 ms 175312 KB Output is correct
18 Correct 68 ms 175460 KB Output is correct