oj.uz

Submission #674687

# Submission time Handle Problem Language Result Execution time Memory
674687 2022-12-25T19:21:33 Z vjudge1 Kamenčići (COCI21_kamencici) C++17
70 / 70
 134 ms 335984 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
 
#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define int long long
#define ld long double
const int INF = 4e18;

int n, k;
string s;
vi pref;

const int N = 350;
int dp[N][N][N];

bool win(int l, int r, int cnt){
    if(cnt >= k) return dp[l][r][cnt] = 0;
    int h = pref[n]-(pref[r+1]-pref[l])-cnt;
    if(h >= k) return dp[l][r][cnt] = 1;

    if(dp[l+1][r][h] == -1)
         dp[l+1][r][h] = win(l+1, r, h);
    if(!dp[l+1][r][h]) return 1;
    if(dp[l][r-1][h] == -1)
         dp[l][r-1][h] = win(l, r-1, h);
    if(!dp[l][r-1][h]) return 1;
    return 0;
}

void solve(){
    cin >> n >> k >> s;
    pref = vi(n+1);

    for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
    for(int k=0; k<N; k++)
        dp[i][j][k] = -1;

    for(int i=0; i<n; i++)
        pref[i+1] = pref[i]+(s[i] == 'C' ? 1 : 0);

    cout << (win(0, n-1, 0) ? "DA\n" : "NE\n");
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif

    int tt = 1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

Compilation message

Main.cpp: In function 'bool win(long long int, long long int, long long int)':
Main.cpp:34:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |     if(cnt >= k) return dp[l][r][cnt] = 0;
      |                         ~~~~~~~~~~~~~~^~~
Main.cpp:36:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   36 |     if(h >= k) return dp[l][r][cnt] = 1;
      |                       ~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 335820 KB Output is correct
2 Correct 128 ms 335812 KB Output is correct
3 Correct 125 ms 335824 KB Output is correct
4 Correct 133 ms 335884 KB Output is correct
5 Correct 127 ms 335808 KB Output is correct
6 Correct 118 ms 335836 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 335820 KB Output is correct
2 Correct 128 ms 335812 KB Output is correct
3 Correct 125 ms 335824 KB Output is correct
4 Correct 133 ms 335884 KB Output is correct
5 Correct 127 ms 335808 KB Output is correct
6 Correct 118 ms 335836 KB Output is correct
7 Correct 119 ms 335876 KB Output is correct
8 Correct 120 ms 335892 KB Output is correct
9 Correct 121 ms 335984 KB Output is correct
10 Correct 118 ms 335856 KB Output is correct
11 Correct 118 ms 335876 KB Output is correct
12 Correct 118 ms 335808 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 335820 KB Output is correct
2 Correct 128 ms 335812 KB Output is correct
3 Correct 125 ms 335824 KB Output is correct
4 Correct 133 ms 335884 KB Output is correct
5 Correct 127 ms 335808 KB Output is correct
6 Correct 118 ms 335836 KB Output is correct
7 Correct 119 ms 335876 KB Output is correct
8 Correct 120 ms 335892 KB Output is correct
9 Correct 121 ms 335984 KB Output is correct
10 Correct 118 ms 335856 KB Output is correct
11 Correct 118 ms 335876 KB Output is correct
12 Correct 118 ms 335808 KB Output is correct
13 Correct 121 ms 335820 KB Output is correct
14 Correct 134 ms 335948 KB Output is correct
15 Correct 121 ms 335832 KB Output is correct
16 Correct 127 ms 335928 KB Output is correct
17 Correct 129 ms 335916 KB Output is correct
18 Correct 123 ms 335864 KB Output is correct