Submission #976079

#	Time	Username	Problem	Language	Result	Execution time	Memory
976079		duckindog	Popeala (CEOI16_popeala)	C++17	17 / 100	513 ms	15952 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74