oj.uz

Submission #728569

# Submission time Handle Problem Language Result Execution time Memory
728569 2023-04-22T16:01:15 Z aykhn Kamenčići (COCI21_kamencici) C++14
70 / 70
 197 ms 179968 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount

int k;
string s;

bool player2(int l, int r, int cnt1, int cnt2);

vector<vector<vector<short>>> dp1(351, vector<vector<short>> (351, vector<short> (351, -1)));
vector<vector<vector<short>>> dp2(351, vector<vector<short>> (351, vector<short> (351, -1)));

bool player1(int l, int r, int cnt1, int cnt2)// a || b || c
{
    if (cnt2 == k) return true;
    if (dp1[l][r][cnt2] != -1) return dp1[l][r][cnt2];
    
    bool a, b;
    a = b = false;
    
    if (s[l] == 'C') a = player2(l + 1, r, cnt1 + 1, cnt2);
    else a = player2(l + 1, r, cnt1, cnt2);
    if (s[r] == 'C') b = player2(l, r - 1, cnt1 + 1, cnt2);
    else b = player2(l, r - 1, cnt1, cnt2);
    
    return dp1[l][r][cnt2] = (a || b);
}

bool player2(int l, int r, int cnt1, int cnt2)// a && b && c
{
    if (cnt1 == k) return false;
    if (dp2[l][r][cnt1] != -1) return dp2[l][r][cnt1];
    
    bool a, b;
    a = b = false;
    
    if (s[l] == 'C') a = player1(l + 1, r, cnt1, cnt2 + 1);
    else a = player1(l + 1, r, cnt1, cnt2);
    if (s[r] == 'C') b = player1(l, r - 1, cnt1, cnt2 + 1);
    else b = player1(l, r - 1, cnt1, cnt2);
    
    return dp2[l][r][cnt1] = (a && b);
}


int main()
{
	int n;
    cin >> n >> k;
    cin >> s;
    
    cout << (player1(0, n - 1, 0, 0) ? "DA" : "NE") << endl;
    return 0;
}

Compilation message

Main.cpp: In function 'bool player1(int, int, int, int)':
Main.cpp:39:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   39 |     return dp1[l][r][cnt2] = (a || b);
Main.cpp: In function 'bool player2(int, int, int, int)':
Main.cpp:55:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   55 |     return dp2[l][r][cnt1] = (a && b);

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 179864 KB Output is correct
2 Correct 152 ms 179920 KB Output is correct
3 Correct 154 ms 179968 KB Output is correct
4 Correct 142 ms 179860 KB Output is correct
5 Correct 146 ms 179872 KB Output is correct
6 Correct 151 ms 179824 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 179864 KB Output is correct
2 Correct 152 ms 179920 KB Output is correct
3 Correct 154 ms 179968 KB Output is correct
4 Correct 142 ms 179860 KB Output is correct
5 Correct 146 ms 179872 KB Output is correct
6 Correct 151 ms 179824 KB Output is correct
7 Correct 152 ms 179900 KB Output is correct
8 Correct 148 ms 179968 KB Output is correct
9 Correct 145 ms 179816 KB Output is correct
10 Correct 171 ms 179880 KB Output is correct
11 Correct 144 ms 179880 KB Output is correct
12 Correct 150 ms 179852 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 179864 KB Output is correct
2 Correct 152 ms 179920 KB Output is correct
3 Correct 154 ms 179968 KB Output is correct
4 Correct 142 ms 179860 KB Output is correct
5 Correct 146 ms 179872 KB Output is correct
6 Correct 151 ms 179824 KB Output is correct
7 Correct 152 ms 179900 KB Output is correct
8 Correct 148 ms 179968 KB Output is correct
9 Correct 145 ms 179816 KB Output is correct
10 Correct 171 ms 179880 KB Output is correct
11 Correct 144 ms 179880 KB Output is correct
12 Correct 150 ms 179852 KB Output is correct
13 Correct 151 ms 179912 KB Output is correct
14 Correct 197 ms 179848 KB Output is correct
15 Correct 159 ms 179900 KB Output is correct
16 Correct 175 ms 179904 KB Output is correct
17 Correct 160 ms 179872 KB Output is correct
18 Correct 157 ms 179904 KB Output is correct