oj.uz

Submission #673102

# Submission time Handle Problem Language Result Execution time Memory
673102 2022-12-19T16:48:53 Z Half Kamenčići (COCI21_kamencici) C++17
70 / 70
 43 ms 20428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cout.precision(20);

    ll k, n;
    cin >> n >> k;
    bool dp[k+1][n][n];
   	string row;
   	cin >> row;
   	ll cs[n+1];
   	cs[0] = 0;
   	for(ll i = 0; i < n; ++i){
   		cs[i+1] = cs[i] + (row[i] == 'C');
   	}
   	ll totc = cs[n];
   	for(ll i = 0; i < n; ++i)for(ll j = 0; j < n; ++j){
		dp[k][i][j] = false;
	}
   	for(ll l = 0; l < n; ++l){
   		for(ll i = 0; i+l < n; ++i){
   			for(ll ki = 0; ki < k; ++ki){
   				ll otk = totc-(cs[i+l+1]-cs[i])-ki;
   				if(otk >= k){
   					dp[ki][i][i+l] = true;
   				}else{
   					if(!dp[otk][i+1][i+l] || !dp[otk][i][i+l-1]){
   						dp[ki][i][i+l] = true;
   					}else{
   						dp[ki][i][i+l] = false;
   					}
   				}
   			}
   		}
   	}
   	cout << (dp[0][0][n-1]?"DA\n":"NE\n");


	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 3 ms 3668 KB Output is correct
14 Correct 7 ms 5076 KB Output is correct
15 Correct 3 ms 2388 KB Output is correct
16 Correct 20 ms 12684 KB Output is correct
17 Correct 43 ms 20428 KB Output is correct
18 Correct 18 ms 12628 KB Output is correct