oj.uz

Submission #650989

# Submission time Handle Problem Language Result Execution time Memory
650989 2022-10-16T09:41:41 Z ktkerem Kamenčići (COCI21_kamencici) C++17
70 / 70
 190 ms 365632 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
/*typedef __int128 vll;
typedef unsigned __int128 uvll;*/
#define llll std::pair<ll , ll>
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e15+7; 
const ll ous = 2e5 + 7;
const ll dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0,1,0,-1};
std::vector<ll> ar(360);
ll dp[360][360][360];
ll n , k;
ll solv(ll i , ll j , ll tkz){
    ll p = dp[i][j][tkz];
    if(p == -1){
        ll bp = (i == 0?0:ar[i-1]) + (ar[n-1] - ar[j]) - tkz;
        if(tkz >= k){
            p = 0;
        }
        else if(bp >= k){
            p = 1;
        }
        else{
            if(!solv(i+1 , j , bp) || !solv(i , j-1 , bp)){
                p = 1;
            }
            else{
                p = 0;
            }
        }
    }
    dp[i][j][tkz] = p;
    return p;
}
void solve(){
    std::cin >> n >> k;
    std::string h;std::cin >> h;
    h.pb('0');
    memset(dp , -1 , sizeof(dp));
    ar[0] = h[0] == 'C';
    for(ll i = 1;n>=i;i++){
        ar[i] = ar[i-1] + (h[i] == 'C');
    }
    ll u = solv(0 , n-1 , 0);
    if(u){
        std::cout << "DA\n";
    }
    else{
        std::cout << "NE\n";
    }
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0;
}

Compilation message

Main.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
Main.cpp: In function 'int main()':
Main.cpp:70:8: warning: unused variable 'o' [-Wunused-variable]
   70 |     ll o = 1;
      |        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 365492 KB Output is correct
2 Correct 135 ms 365400 KB Output is correct
3 Correct 146 ms 365468 KB Output is correct
4 Correct 149 ms 365516 KB Output is correct
5 Correct 137 ms 365468 KB Output is correct
6 Correct 139 ms 365416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 365492 KB Output is correct
2 Correct 135 ms 365400 KB Output is correct
3 Correct 146 ms 365468 KB Output is correct
4 Correct 149 ms 365516 KB Output is correct
5 Correct 137 ms 365468 KB Output is correct
6 Correct 139 ms 365416 KB Output is correct
7 Correct 144 ms 365392 KB Output is correct
8 Correct 164 ms 365460 KB Output is correct
9 Correct 151 ms 365484 KB Output is correct
10 Correct 177 ms 365460 KB Output is correct
11 Correct 158 ms 365480 KB Output is correct
12 Correct 162 ms 365396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 365492 KB Output is correct
2 Correct 135 ms 365400 KB Output is correct
3 Correct 146 ms 365468 KB Output is correct
4 Correct 149 ms 365516 KB Output is correct
5 Correct 137 ms 365468 KB Output is correct
6 Correct 139 ms 365416 KB Output is correct
7 Correct 144 ms 365392 KB Output is correct
8 Correct 164 ms 365460 KB Output is correct
9 Correct 151 ms 365484 KB Output is correct
10 Correct 177 ms 365460 KB Output is correct
11 Correct 158 ms 365480 KB Output is correct
12 Correct 162 ms 365396 KB Output is correct
13 Correct 170 ms 365436 KB Output is correct
14 Correct 169 ms 365568 KB Output is correct
15 Correct 166 ms 365432 KB Output is correct
16 Correct 190 ms 365632 KB Output is correct
17 Correct 164 ms 365456 KB Output is correct
18 Correct 156 ms 365484 KB Output is correct