oj.uz

Submission #976484

# Submission time Handle Problem Language Result Execution time Memory
976484 2024-05-06T15:23:06 Z duckindog Popeala (CEOI16_popeala) C++17
100 / 100
 267 ms 12312 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 10,
          T = 20'000 + 10;
int n, t, s;
int point[T], d[T];
bool b[T][N];
int last[T][N];

int f[N][T];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);


  cin >> n >> t >> s;
  for (int i = 1; i <= t; ++i) cin >> point[i];
  for (int i = 1; i <= n; ++i) { 
    string s; cin >> s;
    for (int j = 1; j <= t; ++j) b[j][i] = (s[j - 1] == '1');
  }

  for (int i = 1; i <= t; ++i) d[i] = d[i - 1] + point[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= t; ++j) last[j][i] = (!b[j][i] ? j : last[j - 1][i]);
  }

  for (int i = 1; i <= t; ++i) { 
    last[i][0] = i;
    sort(last[i], last[i] + n + 1);
  }

  memset(f, 127, sizeof f);
  f[0][0] = 0;
  for (int i = 1; i <= s; ++i) {
    vector<int> best(n + 1, 2'000'000'000);
    for (int j = 1; j <= t; ++j) {
      for (int cnt = 0; cnt <= n; ++cnt) {
        for (int it = last[j - 1][cnt]; it < last[j][cnt]; ++it) 
          best[cnt] = min(best[cnt], f[i - 1][it] - cnt * d[it]);
        f[i][j] = min(f[i][j], best[cnt] + cnt * d[j]);
      }
    }
  }

  for (int i = 1; i <= s; ++i) cout << f[i][t] << "\n";
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8796 KB Output is correct
2 Correct 7 ms 7260 KB Output is correct
3 Correct 9 ms 7260 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7772 KB Output is correct
2 Correct 51 ms 8280 KB Output is correct
3 Correct 48 ms 8280 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7000 KB Output is correct
3 Correct 10 ms 8796 KB Output is correct
4 Correct 7 ms 7260 KB Output is correct
5 Correct 9 ms 7260 KB Output is correct
6 Correct 36 ms 7772 KB Output is correct
7 Correct 51 ms 8280 KB Output is correct
8 Correct 48 ms 8280 KB Output is correct
9 Correct 75 ms 9052 KB Output is correct
10 Correct 120 ms 11356 KB Output is correct
11 Correct 196 ms 12276 KB Output is correct
12 Correct 230 ms 12152 KB Output is correct
13 Correct 267 ms 12116 KB Output is correct
14 Correct 260 ms 12304 KB Output is correct
15 Correct 249 ms 12312 KB Output is correct