Submission #1087529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087529		juicy	Popeala (CEOI16_popeala)	C++17	0 / 100	49 ms	1116 KiB

popeala

#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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74