Submission #570349

#	Time	Username	Problem	Language	Result	Execution time	Memory
570349		600Mihnea	Popeala (CEOI16_popeala)	C++17	26 / 100	2043 ms	4820 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

 /// freopen ("input.txt", "r", stdin);

  const int INF_INT = (int) 2e9 + 7;

  int n, t, s;
  cin >> n >> t >> s;

  vector<int> points(t), sum(t + 1, 0);
  vector<vector<int>> v(n, vector<int> (t, 0)), pref(n, vector<int> (t + 1, 0));
  vector<pair<int, int>> last0(n);

  for (int i = 0; i < n; i++) {
    last0[i] = {0, i};
  }

  for (int i = 0; i < t; i++) {
    cin >> points[i];
    sum[i + 1] = sum[i] + points[i];
  }

  for (int i = 0; i < n; i++) {
    string str;
    cin >> str;
    assert((int) str.size() == t);
    for (int j = 0; j < t; j++) {
      v[i][j] = str[j] - '0';
      assert(v[i][j] == 0 || v[i][j] == 1);
      pref[i][j + 1] = pref[i][j] + v[i][j];
    }
  }

  vector<vector<int>> dp(t + 1, vector<int> (s + 1, INF_INT));

  dp[0][0] = 0;
  for (int r = 1; r <= t; r++) {
    vector<int> where(n);
    for (int i = 0; i < n; i++) {
      where[last0[i].second] = i;
    }
    for (int i = 0; i < n; i++) {
      if (v[i][r - 1] == 0) {
        last0[where[i]].first = r;
        assert(last0[where[i]].second == i);
      }
    }
    sort(last0.begin(), last0.end());
    for (int here = 1; here <= s; here++) {

      /// compute dp[r][t]
      int best = INF_INT;
      int cnt = 0;
      for (int l = 1; l <= r; l++) {
        while (cnt < n && last0[cnt].first < l) {
          cnt++;
        }
        best = min((ll) best, (ll) dp[l - 1][here - 1] + cnt * (sum[r] - sum[l - 1]));
      }
      dp[r][here] = best;
    }
  }
  for (int i = 1; i <= s; i++) {
    cout << dp[t][i] << "\n";
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74