#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)55;
const int MAXT = (int)2e5 + 3;
const ll infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18 + 3;
typedef long long lint;
typedef pair<lint, int> pli;
#define fi first
#define se second
int N, T, S;
int P[MAXT];
char R[MAXN][MAXT];
int sp[MAXT];
lint dp[MAXN][MAXT];
lint seg[MAXN][MAXT];
vector<int> wro[MAXN];
int ch[MAXT][MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> T >> S;
for(int i = 1; i <= T; i++) cin >> P[i];
for(int i = 0; i < N; i++) cin >> R[i];
for(int i = 1; i <= T; i++) sp[i] = sp[i - 1] + P[i];
for(int i = 0; i < N; i++) {
wro[i].push_back(0);
for(int j = 0; j < T; j++) if(R[i][j] == '0') wro[i].push_back(j + 1);
}
for(int i = 1; i <= S; i++) dp[i][0] = LINF;
for(int i = 1; i <= T; i++) dp[0][i] = LINF;
for(int j = 1; j <= T; j++) {
for(int k = 0; k < N; k++) ch[j][k] = *prev(upper_bound(wro[k].begin(), wro[k].end(), j));
ch[j][N] = 0;
ch[j][N + 1] = j;
sort(ch[j], ch[j] + N + 2);
}
for(int i = 1; i <= S; i++) {
for(int j = 0; j <= N; j++) for(int k = 0; k < T; k++) seg[j][k] = dp[i - 1][k] - j * sp[k];
for(int j = 1; j <= T; j++) dp[i][j] = LINF;
for(int j = 0; j <= N; j++) {
deque<pli> dq;
ch[0][j + 1] = 0;
for(int k = 1; k <= T; k++) {
for(int l = ch[k - 1][j + 1]; l < ch[k][j + 1]; l++) {
while(!dq.empty() && dq.back().fi > seg[j][l]) dq.pop_back();
dq.push_back(make_pair(seg[j][l], l));
}
while(!dq.empty() && dq.front().se < ch[k][j]) dq.pop_front();
if(!dq.empty()) dp[i][k] = min(dp[i][k], dq.front().fi + sp[k] * j);
}
}
}
for(int i = 1; i <= S; i++) cout << dp[i][T] << "\n";
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:36:41: error: 'LINF' was not declared in this scope
for(int i = 1; i <= S; i++) dp[i][0] = LINF;
^~~~
popeala.cpp:36:41: note: suggested alternative: 'SING'
for(int i = 1; i <= S; i++) dp[i][0] = LINF;
^~~~
SING
popeala.cpp:37:41: error: 'LINF' was not declared in this scope
for(int i = 1; i <= T; i++) dp[0][i] = LINF;
^~~~
popeala.cpp:37:41: note: suggested alternative: 'SING'
for(int i = 1; i <= T; i++) dp[0][i] = LINF;
^~~~
SING
popeala.cpp:46:42: error: 'LINF' was not declared in this scope
for(int j = 1; j <= T; j++) dp[i][j] = LINF;
^~~~
popeala.cpp:46:42: note: suggested alternative: 'SING'
for(int j = 1; j <= T; j++) dp[i][j] = LINF;
^~~~
SING
