Submission #1264985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264985		herominhsteve	Kamenčići (COCI21_kamencici)	C++20	70 / 70	83 ms	169544 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 351;

int n,K;
string str;
vector<int> pre;
int totalRed;

void init(){
	cin>>n>>K>>str;
	pre.assign(n+1,0);
	for (int i=1;i<=n;i++){
		pre[i] = pre[i-1] + (str[i-1]=='C');
	}
	totalRed = pre[n];
}

// ! dp[l][r][taken]
int dp[MAXN][MAXN][MAXN];

int canWin(int l,int r,int taken){
	int &res = dp[l][r][taken];
	if (~res) return res;
	int redNotTaken = pre[r] - pre[l-1];
	int otherTaken = totalRed - redNotTaken - taken;
	if (taken>=K) res = 0;
	else if (otherTaken>=K) res=1;
	else{
		if (!canWin(l+1,r,otherTaken) or !canWin(l,r-1,otherTaken)) res = 1;
		else res = 0;
	}
	return res;
}

void sol(){
	mset(dp,-1);
	cout<< (canWin(1,n,0) ? "DA" : "NE");
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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