oj.uz

Submission #570348

# Submission time Handle Problem Language Result Execution time Memory
570348 2022-05-29T09:31:49 Z 600Mihnea Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 1748 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));

  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++) {
    for (int here = 1; here <= s; here++) {
      /// compute dp[r][t]
      int best = INF_INT;
      for (int l = 1; l <= r; l++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
          if (pref[i][r] - pref[i][l - 1] == r - l + 1) {
            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 1 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 357 ms 656 KB Output is correct
2 Correct 306 ms 656 KB Output is correct
3 Correct 331 ms 660 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 357 ms 656 KB Output is correct
4 Correct 306 ms 656 KB Output is correct
5 Correct 331 ms 660 KB Output is correct
6 Execution timed out 2089 ms 1748 KB Time limit exceeded
7 Halted 0 ms 0 KB -