oj.uz

Submission #1087529

# Submission time Handle Problem Language Result Execution time Memory
1087529 2024-09-12T21:02:27 Z juicy Popeala (CEOI16_popeala) C++17
0 / 100
 49 ms 1116 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 20005, D = 50, inf = 2e9 + 1;

int n, t, s;
int a[N], dp[N], f[N];
array<int, D> pf[N];

int qry(int l, int r) {
  int res = 0;
  for (int i = 0; i < n; ++i) {
    if (pf[r][i] - pf[l - 1][i] == r - l + 1) {
      res += a[r] - a[l - 1];
    }
  }
  return res;
}

void dc(int l, int r, int u, int v) {
  if (l > r) {
    return;
  }
  int m = (l + r) / 2;
  array<int, 2> best = {inf, -1};
  for (int i = u; i <= min(v, m); ++i) {
    if (f[i - 1] != inf) {
      best = min(best, {f[i - 1] + qry(i, m), i});
    }
  }
  dp[m] = best[0];
  dc(l, m - 1, u, best[1]);
  dc(m + 1, r, best[1], v);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> t >> s;
  for (int i = 1; i <= t; ++i) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  for (int i = 0; i < n; ++i) {
    string s; cin >> s;
    for (int j = 0; j < t; ++j) {
      pf[j + 1][i] = pf[j][i] + (s[j] == '1');
    }
  }
  fill(f + 1, f + t + 1, inf);
  for (int i = 1; i <= s; ++i) {
    dc(i, t, i, t);
    cout << dp[t] << "\n";
    swap(f, dp);
  }
  return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -