This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int MAX = 2e4 + 5;
int n, t, s, dp[55][MAX], p[MAX], ix[MAX][55], cand[55], ii[55];
string w;
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> t >> s;
for(int i = 1; i <= t; i++) cin >> p[i], p[i] += p[i - 1];
for(int i = 1; i <= n; i++){
cin >> w;
for(int j = 1; j <= t; j++) ix[j][i - 1] = (w[j - 1] - '0') ? ix[j - 1][i - 1] : j;
}
for(int i = 1; i <= t; i++) sort(ix[i], ix[i] + n);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= s; i++){
memset(cand, 0x3f, sizeof(cand));
memset(ii, 0, sizeof(ii));
for(int j = 1; j <= t; j++){
dp[i][j] = dp[i - 1][j - 1] + n * (p[j] - p[j - 1]);
for(int k = 0; k < n; k++){
while(ii[k] < ix[j][k]) cand[k] = min(cand[k], dp[i - 1][ii[k]] - k * p[ii[k]]), ii[k]++;
dp[i][j] = min(dp[i][j], cand[k] + k * p[j]);
}
}
cout << dp[i][t] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |