Submission #658377

#	Time	Username	Problem	Language	Result	Execution time	Memory
658377		Foxyy	Kamenčići (COCI21_kamencici)	C++17	70 / 70	56 ms	84820 KiB

Main

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

#define ll long long
#define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);

template <typename T>
struct PrefixSum {
	int n;
	vector<T> sum;
	
	PrefixSum() {}
	PrefixSum(vector<int> vec) : n((int)vec.size()) {
		sum.resize(n+1);
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i-1] + vec[i-1];
		}
	};
	
	T getSum(int l, int r) {
		return sum[r+1] - sum[l];
	}
};

struct Solver {
	int& n;
	int& k;
	string& pebbles;
	
	void solve() {
		vector<vector<vector<int>>> dp(
			n, vector<vector<int>>(
				n, vector<int>(k+1)
			)
		); // 0: state not calculated, 1: losing state, 2: winning state
		
		PrefixSum<int> redSum;
		/* get redPebbleSum */ {
			vector<int> cnt(n);
			for (int i = 0; i < n; i++) if (pebbles[i] == 'C') {
				cnt[i] = 1;
			}
			redSum = PrefixSum<int>(cnt);
		};
		
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				dp[i][j][k] = 1;
			}
		}
		
		for (int len = 1; len <= n; len++) {
			for (int i = 0, j = len-1; j < n; i++, j++) {
				int currentRedSum = redSum.getSum(0, n-1) - redSum.getSum(i, j);
				for (int redTaken = max(currentRedSum-k+1, 0); redTaken <= min(currentRedSum, k-1); redTaken++) {
					
					/* take left */
					int leftResult = 1;
					if (dp[i+1][j][currentRedSum - redTaken] == 1) {
						leftResult = 2;
					}
					if (pebbles[i] == 'C' and redTaken == k-1) {
						leftResult = 1;
					}
					
					/* take right */
					int rightResult = 1;
					if (dp[i][j-1][currentRedSum - redTaken] == 1) {
						rightResult = 2;
					}
					if (pebbles[j] == 'C' and redTaken == k-1) {
						rightResult = 1;
					}
					
					dp[i][j][redTaken] = max(leftResult, rightResult);
				}
			}
		}
		
		if (dp[0][n-1][0] == 2) {
			cout << "DA\n";
		} else {
			cout << "NE\n";
		}
	}
};

signed main() {
	Foxyy
	
	int T = 1;
//	cin >> T;
	while(T--) {
		int n, k;
		cin >> n >> k;
		string pebbles;
		cin >> pebbles;
		
		Solver solver{n, k, pebbles};
		solver.solve();
	}
}

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