oj.uz

Submission #570352

# Submission time Handle Problem Language Result Execution time Memory
570352 2022-05-29T09:56:07 Z 600Mihnea Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 1620 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] = {1, 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 + 1;
        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;
      for (int coef = 0; coef <= n; coef++) {
        int cnt = 0, L, R;
        if (coef == 0) {
          L = 0;
        } else {
          L = last0[coef - 1].first;
        }
        if (coef == n) {
          R = r;
        } else {
          R = last0[coef].first;
        }
        for (int l = 1; l <= r; l++) {
          while (cnt < n && last0[cnt].first <= l) {
            cnt++;
          }
          if (cnt == coef) {
            assert(l >= L);
            ///assert(r <= R);
            best = min((ll) best, (ll) dp[l - 1][here - 1] + coef * (sum[r] - sum[l - 1]));
          }
        }
      }
      dp[r][here] = best;
    }
  }
  for (int i = 1; i <= s; i++) {
    cout << dp[t][i] << "\n";
  }
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:60:25: warning: variable 'R' set but not used [-Wunused-but-set-variable]
   60 |         int cnt = 0, L, R;
      |                         ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 644 KB Output is correct
2 Correct 722 ms 620 KB Output is correct
3 Correct 732 ms 628 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 1620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 700 ms 644 KB Output is correct
4 Correct 722 ms 620 KB Output is correct
5 Correct 732 ms 628 KB Output is correct
6 Execution timed out 2076 ms 1620 KB Time limit exceeded
7 Halted 0 ms 0 KB -