oj.uz

Submission #570349

# Submission time Handle Problem Language Result Execution time Memory
570349 2022-05-29T09:39:32 Z 600Mihnea Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 4820 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 656 KB Output is correct
2 Correct 14 ms 636 KB Output is correct
3 Correct 16 ms 644 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 1688 KB Output is correct
2 Correct 449 ms 2396 KB Output is correct
3 Correct 795 ms 3148 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 14 ms 656 KB Output is correct
4 Correct 14 ms 636 KB Output is correct
5 Correct 16 ms 644 KB Output is correct
6 Correct 237 ms 1688 KB Output is correct
7 Correct 449 ms 2396 KB Output is correct
8 Correct 795 ms 3148 KB Output is correct
9 Execution timed out 2043 ms 4820 KB Time limit exceeded
10 Halted 0 ms 0 KB -