oj.uz

Submission #976079

# Submission time Handle Problem Language Result Execution time Memory
976079 2024-05-06T07:08:31 Z duckindog Popeala (CEOI16_popeala) C++17
17 / 100
 513 ms 15952 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 10,
          T = 500 + 10;
int n, t, s;
int point[T], d[T];
bool b[N][T], chk[N][T][T];

int f[N][T];

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

  { //input
    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[i][j] = (s[j - 1] == '1');
    }
  }  

  memset(chk, true, sizeof chk);
  for (int i = 1; i <= n; ++i) { 
    for (int l = 1; l <= t; ++l) {
      for (int r = l; r <= t; ++r) chk[i][l][r] = chk[i][l][r - 1] & b[i][r];
    }
  }

  for (int i = 1; i <= t; ++i) d[i] = d[i - 1] + point[i];

  memset(f, 63, sizeof f);
  for (int i = 0; i <= s; ++i) f[i][0] = 0;
  for (int i = 1; i <= s; ++i) { 
    for (int r = i; r <= t; ++r) { 
      auto& ret = f[i][r];
      for (int l = i; l <= r; ++l) { 
        int sum = 0;
        for (int x = 1; x <= n; ++x) sum += chk[x][l][r] * (d[r] - d[l - 1]);
        ret = min(ret, sum + f[i - 1][l - 1]);
      }
    }
  }
  
  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 3 ms 15704 KB Output is correct
2 Correct 3 ms 15704 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 15896 KB Output is correct
2 Correct 461 ms 15888 KB Output is correct
3 Correct 499 ms 15952 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15704 KB Output is correct
2 Correct 3 ms 15704 KB Output is correct
3 Correct 513 ms 15896 KB Output is correct
4 Correct 461 ms 15888 KB Output is correct
5 Correct 499 ms 15952 KB Output is correct
6 Runtime error 2 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -