oj.uz

Submission #898785

# Submission time Handle Problem Language Result Execution time Memory
898785 2024-01-05T06:10:15 Z duckindog Kamenčići (COCI21_kamencici) C++14
70 / 70
 76 ms 365908 KB 
// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 350 + 10;
int n, k;
int a[N], d[N];
int f[N][N][2][N];
bool dp(int l, int r, int t, int x) {
  if (x == k) return 0;
  if (d[l - 1] + d[n] - d[r] - x == k) return 1;
  auto &ret = f[l][r][t][x];
  if (ret > -1) return ret;
  if (t) {
    auto lt = dp(l + 1, r, 1 - t, x + a[l]);
    auto rt = dp(l, r - 1, 1 - t, x + a[r]);
    ret = lt | rt;
  } else {
    auto lt = dp(l + 1, r, 1 - t, x);
    auto rt = dp(l, r - 1, 1 - t, x);
    ret = lt & rt;
  }
  return ret;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.out", "w", stdout);
    freopen("duck.inp", "r", stdin);
  }
  memset(f, -1, sizeof f);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    char x; cin >> x;
    a[i] = x == 'C';
    d[i] = d[i - 1] + a[i];
  }
  cout << (dp(1, n, 1, 0) == 1 ? "DA" : "NE");
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 365396 KB Output is correct
2 Correct 55 ms 365632 KB Output is correct
3 Correct 54 ms 365396 KB Output is correct
4 Correct 54 ms 365416 KB Output is correct
5 Correct 54 ms 365396 KB Output is correct
6 Correct 54 ms 365652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 365396 KB Output is correct
2 Correct 55 ms 365632 KB Output is correct
3 Correct 54 ms 365396 KB Output is correct
4 Correct 54 ms 365416 KB Output is correct
5 Correct 54 ms 365396 KB Output is correct
6 Correct 54 ms 365652 KB Output is correct
7 Correct 53 ms 365648 KB Output is correct
8 Correct 53 ms 365560 KB Output is correct
9 Correct 54 ms 365636 KB Output is correct
10 Correct 53 ms 365652 KB Output is correct
11 Correct 57 ms 365716 KB Output is correct
12 Correct 55 ms 365524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 365396 KB Output is correct
2 Correct 55 ms 365632 KB Output is correct
3 Correct 54 ms 365396 KB Output is correct
4 Correct 54 ms 365416 KB Output is correct
5 Correct 54 ms 365396 KB Output is correct
6 Correct 54 ms 365652 KB Output is correct
7 Correct 53 ms 365648 KB Output is correct
8 Correct 53 ms 365560 KB Output is correct
9 Correct 54 ms 365636 KB Output is correct
10 Correct 53 ms 365652 KB Output is correct
11 Correct 57 ms 365716 KB Output is correct
12 Correct 55 ms 365524 KB Output is correct
13 Correct 54 ms 365648 KB Output is correct
14 Correct 76 ms 365904 KB Output is correct
15 Correct 58 ms 365624 KB Output is correct
16 Correct 75 ms 365908 KB Output is correct
17 Correct 66 ms 365564 KB Output is correct
18 Correct 58 ms 365648 KB Output is correct