oj.uz

Submission #658377

# Submission time Handle Problem Language Result Execution time Memory
658377 2022-11-13T03:53:35 Z Foxyy Kamenčići (COCI21_kamencici) C++17
70 / 70
 56 ms 84820 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 13 ms 18516 KB Output is correct
14 Correct 27 ms 24156 KB Output is correct
15 Correct 12 ms 13268 KB Output is correct
16 Correct 35 ms 54080 KB Output is correct
17 Correct 56 ms 84820 KB Output is correct
18 Correct 34 ms 54100 KB Output is correct