oj.uz

Submission #674710

# Submission time Handle Problem Language Result Execution time Memory
674710 2022-12-26T00:34:57 Z rafatoa Kamenčići (COCI21_kamencici) C++17
70 / 70
 133 ms 336032 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 131 ms 335820 KB Output is correct
2 Correct 130 ms 335840 KB Output is correct
3 Correct 133 ms 335920 KB Output is correct
4 Correct 121 ms 336032 KB Output is correct
5 Correct 122 ms 335824 KB Output is correct
6 Correct 122 ms 335800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 335820 KB Output is correct
2 Correct 130 ms 335840 KB Output is correct
3 Correct 133 ms 335920 KB Output is correct
4 Correct 121 ms 336032 KB Output is correct
5 Correct 122 ms 335824 KB Output is correct
6 Correct 122 ms 335800 KB Output is correct
7 Correct 121 ms 335896 KB Output is correct
8 Correct 128 ms 335824 KB Output is correct
9 Correct 121 ms 335852 KB Output is correct
10 Correct 124 ms 335872 KB Output is correct
11 Correct 124 ms 335908 KB Output is correct
12 Correct 121 ms 335948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 335820 KB Output is correct
2 Correct 130 ms 335840 KB Output is correct
3 Correct 133 ms 335920 KB Output is correct
4 Correct 121 ms 336032 KB Output is correct
5 Correct 122 ms 335824 KB Output is correct
6 Correct 122 ms 335800 KB Output is correct
7 Correct 121 ms 335896 KB Output is correct
8 Correct 128 ms 335824 KB Output is correct
9 Correct 121 ms 335852 KB Output is correct
10 Correct 124 ms 335872 KB Output is correct
11 Correct 124 ms 335908 KB Output is correct
12 Correct 121 ms 335948 KB Output is correct
13 Correct 120 ms 335808 KB Output is correct
14 Correct 132 ms 335848 KB Output is correct
15 Correct 127 ms 335932 KB Output is correct
16 Correct 130 ms 335892 KB Output is correct
17 Correct 123 ms 335876 KB Output is correct
18 Correct 122 ms 335808 KB Output is correct