# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
146784 |
2019-08-26T06:38:18 Z |
lyc |
Popeala (CEOI16_popeala) |
C++14 |
|
501 ms |
6904 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int INF = 2e9+10;
const int MAXT = 20005;
const int MAXN = 55;
const int MAXS = 55;
int N, T, S;
int P[MAXT];
char R[MAXN][MAXT];
int res[MAXS][MAXT];
int cost[MAXT];
vector<int> flip[MAXN];
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> T >> S;
FOR(i,1,T) { cin >> P[i]; P[i] += P[i-1]; }
FOR(i,1,N) {
cin >> (R[i]+1);
FOR(j,1,T) {
if (R[i][j] == '0') flip[i].push_back(j);
}
flip[i].push_back(T+1);
}
//FOR(i,1,N) { FOR(j,1,T) { cout << R[i][j] << " "; } cout << endl; }
res[0][T+1] = 0;
FOR(x,1,S) res[x][T+1] = INF;
FOR(i,1,T) res[0][i] = INF;
FOR(x,1,S) {
int nxt[N+1]; FOR(i,1,N) nxt[i] = T+1;
int state[T+1]; FOR(i,1,T) state[i] = -1;
int best[N+1]; FOR(i,0,N) best[i] = INF;
RFOR(i,T,1) {
state[i] = N;
if (res[x-1][i+1] != INF) best[N] = min(best[N], P[i]*N + res[x-1][i+1]);
FOR(m,1,N) if (R[m][i] == '0') {
//cout << "STATE " << state[nxt[m]-1] << " " << state[i] << endl;
FOR(s,state[nxt[m]-1],state[i]) best[s] = INF;
FOR(j,i,nxt[m]-1) {
//cout << state[j]-1 << " AAAAA " << P[j]*state[j] + res[x-1][j+1] << endl;
--state[j];
if (res[x-1][j+1] != INF) best[state[j]] = min(best[state[j]], P[j]*state[j] + res[x-1][j+1]);
}
nxt[m] = i;
}
res[x][i] = INF;
FOR(s,0,N) if (best[s] != INF) res[x][i] = min(res[x][i], -P[i-1]*s + best[s]);
//FOR(j,i,T) {
// int nxt = res[x-1][j+1];
// if (nxt != INF) res[x][i] = min(res[x][i], nxt + (P[j]-P[i-1])*state[j]);
//}
//FOR(j,1,T) { cout << state[j] << ' '; } cout << endl;
//FOR(s,0,N) { cout << best[s] << ' '; } cout << endl;
//cout << x << " " << i << " :: " << res[x][i] << endl;
}
}
FOR(i,1,S) cout << res[i][1] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
888 KB |
Output is correct |
2 |
Correct |
13 ms |
888 KB |
Output is correct |
3 |
Correct |
14 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
1608 KB |
Output is correct |
2 |
Correct |
77 ms |
1664 KB |
Output is correct |
3 |
Correct |
89 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
14 ms |
888 KB |
Output is correct |
4 |
Correct |
13 ms |
888 KB |
Output is correct |
5 |
Correct |
14 ms |
888 KB |
Output is correct |
6 |
Correct |
56 ms |
1608 KB |
Output is correct |
7 |
Correct |
77 ms |
1664 KB |
Output is correct |
8 |
Correct |
89 ms |
2040 KB |
Output is correct |
9 |
Correct |
141 ms |
2808 KB |
Output is correct |
10 |
Correct |
197 ms |
3536 KB |
Output is correct |
11 |
Correct |
431 ms |
6560 KB |
Output is correct |
12 |
Correct |
450 ms |
6904 KB |
Output is correct |
13 |
Correct |
501 ms |
6752 KB |
Output is correct |
14 |
Correct |
497 ms |
6852 KB |
Output is correct |
15 |
Correct |
485 ms |
6824 KB |
Output is correct |