oj.uz

Submission #976078

# Submission time Handle Problem Language Result Execution time Memory
976078 2024-05-06T07:07:50 Z duckindog Popeala (CEOI16_popeala) C++17
0 / 100
 324 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 10,
          T = 4'000 + 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 324 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Runtime error 324 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -