oj.uz

Submission #974066

# Submission time Handle Problem Language Result Execution time Memory
974066 2024-05-02T17:37:26 Z VinhLuu Kamenčići (COCI21_kamencici) C++17
70 / 70
 86 ms 175696 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 350 + 5;
const int oo = 1e9 + 1;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

int n, k, dp[N][N][N], p[N];
string s;

int solve(int l, int r, int K) {
	if(dp[l][r][K] != -1) return dp[l][r][K];
	if(K >= k) return dp[l][r][K] = 0;
	if(p[n] - p[r] + p[l - 1] - K >= k) return dp[l][r][K] = 1;
	if ((n - (r - l + 1)) % 2) return dp[l][r][K] = (solve(l + 1, r, K) & solve(l, r - 1, K));
	return dp[l][r][K] = (solve(l + 1, r, K + (s[l] == 'C')) | solve(l, r - 1, K + (s[r] == 'C')));
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    memset(dp, -1, sizeof(dp));
	cin >> n >> k >> s;
	s = " " + s;

	for (int i = 1; i <= n; i++) p[i] = p[i - 1] + (s[i] == 'C');
    cout << (solve(1, n, 0) ? "DA" : "NE") << "\n";
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 175444 KB Output is correct
2 Correct 25 ms 175452 KB Output is correct
3 Correct 26 ms 175452 KB Output is correct
4 Correct 26 ms 175360 KB Output is correct
5 Correct 24 ms 175444 KB Output is correct
6 Correct 25 ms 175444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 175444 KB Output is correct
2 Correct 25 ms 175452 KB Output is correct
3 Correct 26 ms 175452 KB Output is correct
4 Correct 26 ms 175360 KB Output is correct
5 Correct 24 ms 175444 KB Output is correct
6 Correct 25 ms 175444 KB Output is correct
7 Correct 26 ms 175696 KB Output is correct
8 Correct 25 ms 175440 KB Output is correct
9 Correct 25 ms 175484 KB Output is correct
10 Correct 25 ms 175444 KB Output is correct
11 Correct 25 ms 175452 KB Output is correct
12 Correct 25 ms 175412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 175444 KB Output is correct
2 Correct 25 ms 175452 KB Output is correct
3 Correct 26 ms 175452 KB Output is correct
4 Correct 26 ms 175360 KB Output is correct
5 Correct 24 ms 175444 KB Output is correct
6 Correct 25 ms 175444 KB Output is correct
7 Correct 26 ms 175696 KB Output is correct
8 Correct 25 ms 175440 KB Output is correct
9 Correct 25 ms 175484 KB Output is correct
10 Correct 25 ms 175444 KB Output is correct
11 Correct 25 ms 175452 KB Output is correct
12 Correct 25 ms 175412 KB Output is correct
13 Correct 25 ms 175696 KB Output is correct
14 Correct 70 ms 175564 KB Output is correct
15 Correct 28 ms 175428 KB Output is correct
16 Correct 37 ms 175452 KB Output is correct
17 Correct 31 ms 175440 KB Output is correct
18 Correct 27 ms 175452 KB Output is correct