Submission #1147047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147047		Unforgettablepl	Kamenčići (COCI21_kamencici)	C++20	70 / 70	93 ms	167752 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int modulo = 1e9+7;
const int INF = 1e15;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin >> n >> k;
	vector<bool> grid(n+1);
	vector<int> P(n+1);
	for(int i=1;i<=n;i++){
		char a;cin>>a;
		grid[i]=a=='C';
		if(grid[i])P[i]=1;
		P[i]+=P[i-1];
	}
	vector DP(n+1,vector(n+1,vector<int>(k+1)));
	for(int l=n;l;l--){
		for(int r=l;r<=n;r++){
			for(int x=0;x<=k;x++){
				int other = P[n]-P[r]+P[l-1]-x;
				if(other>k or other<0)continue;
				if(other==k and x==k)continue; // Meaningless states
				if(other==k){DP[l][r][x]=1;continue;}
				if(x==k or l==r){DP[l][r][x]=2;continue;} // Exit states
				if(DP[l+1][r][other]==2 or DP[l][r-1][other]==2)DP[l][r][x]=1;
				else DP[l][r][x]=2;
			}
		}
	}
	if(DP[1][n][0]==1)cout<<"DA\n";
	else cout<<"NE\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40