oj.uz

Submission #898784

# Submission time Handle Problem Language Result Execution time Memory
898784 2024-01-05T06:09:20 Z duckindog Kamenčići (COCI21_kamencici) C++14
10 / 70
 1000 ms 365656 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]);
    return lt | rt;
  } else {
    auto lt = dp(l + 1, r, 1 - t, x);
    auto rt = dp(l, r - 1, 1 - t, x);
    return lt & rt;
  }
}

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

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  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:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 365556 KB Output is correct
2 Correct 57 ms 365424 KB Output is correct
3 Correct 64 ms 365644 KB Output is correct
4 Correct 59 ms 365656 KB Output is correct
5 Correct 57 ms 365652 KB Output is correct
6 Correct 56 ms 365428 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 365556 KB Output is correct
2 Correct 57 ms 365424 KB Output is correct
3 Correct 64 ms 365644 KB Output is correct
4 Correct 59 ms 365656 KB Output is correct
5 Correct 57 ms 365652 KB Output is correct
6 Correct 56 ms 365428 KB Output is correct
7 Correct 71 ms 365648 KB Output is correct
8 Correct 66 ms 365468 KB Output is correct
9 Execution timed out 1069 ms 365572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 365556 KB Output is correct
2 Correct 57 ms 365424 KB Output is correct
3 Correct 64 ms 365644 KB Output is correct
4 Correct 59 ms 365656 KB Output is correct
5 Correct 57 ms 365652 KB Output is correct
6 Correct 56 ms 365428 KB Output is correct
7 Correct 71 ms 365648 KB Output is correct
8 Correct 66 ms 365468 KB Output is correct
9 Execution timed out 1069 ms 365572 KB Time limit exceeded
10 Halted 0 ms 0 KB -