oj.uz

Submission #872762

# Submission time Handle Problem Language Result Execution time Memory
872762 2023-11-13T17:17:29 Z tsumondai Kamenčići (COCI21_kamencici) C++14
70 / 70
 28 ms 177116 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e9, mod = 1e9 + 7;
 
int n, m, k, a[N], dp[355][355][355];
string s;
vector<int> arr;

/*
A di truoc
C: do ; P:xanh
Neu a thang => DA
Khong quan tam nguoi kia di nhu the nao
Con khong thi NE
*/

int calc(int l, int r, int uk) {
	int &res= dp[l][r][uk];
	if (res==-1) {
		int total_red=a[n]; 
		int left_red=a[r]-a[l-1];
		int other_red=total_red-left_red-uk;
		if (uk>=k) {
			res=0;
		} else if (other_red>=k) {
			res=1;
		} else {
			if (!calc(l+1, r, other_red) || !calc(l,r-1, other_red)) {
				res=1;
			} else {
				res=0;
			}
		}
	}
	return res;
}

void process() {
	memset(dp, -1, sizeof(dp));
	cin >> n >> k;
	cin >> s;
	s=' ' + s;
	foru(i,1,n) if (s[i]=='C') a[i]=1; else a[i]=0;
	foru(i,1,n) a[i]+=a[i-1];
	if (calc(1,n,0)) {
		cout << "DA";
	} else {
		cout << "NE";
	}
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 176920 KB Output is correct
2 Correct 20 ms 176892 KB Output is correct
3 Correct 23 ms 176984 KB Output is correct
4 Correct 23 ms 176988 KB Output is correct
5 Correct 20 ms 176988 KB Output is correct
6 Correct 21 ms 176896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 176920 KB Output is correct
2 Correct 20 ms 176892 KB Output is correct
3 Correct 23 ms 176984 KB Output is correct
4 Correct 23 ms 176988 KB Output is correct
5 Correct 20 ms 176988 KB Output is correct
6 Correct 21 ms 176896 KB Output is correct
7 Correct 23 ms 176880 KB Output is correct
8 Correct 20 ms 176988 KB Output is correct
9 Correct 21 ms 177084 KB Output is correct
10 Correct 20 ms 176988 KB Output is correct
11 Correct 20 ms 176988 KB Output is correct
12 Correct 21 ms 176980 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 176920 KB Output is correct
2 Correct 20 ms 176892 KB Output is correct
3 Correct 23 ms 176984 KB Output is correct
4 Correct 23 ms 176988 KB Output is correct
5 Correct 20 ms 176988 KB Output is correct
6 Correct 21 ms 176896 KB Output is correct
7 Correct 23 ms 176880 KB Output is correct
8 Correct 20 ms 176988 KB Output is correct
9 Correct 21 ms 177084 KB Output is correct
10 Correct 20 ms 176988 KB Output is correct
11 Correct 20 ms 176988 KB Output is correct
12 Correct 21 ms 176980 KB Output is correct
13 Correct 21 ms 177116 KB Output is correct
14 Correct 28 ms 177108 KB Output is correct
15 Correct 25 ms 176984 KB Output is correct
16 Correct 27 ms 176980 KB Output is correct
17 Correct 24 ms 176984 KB Output is correct
18 Correct 22 ms 177000 KB Output is correct