#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
int N, T, S;
int points[20005];
int prefixpoints[20005];
bool solves[52][20005];
int presolve[52][20005];
int DP1[20005];
int DP2[20005];
int ranges[20005][52]; //M[j][k] is the min value of i s.t. cnt(i. j) >= k;
int INF = 2000000005;
struct MinDeque {
int lo = 1, hi = 0;
deque<pii> d;
void ins(int x) { // add to back
while (sz(d) && d.back().f >= x) d.pop_back();
d.pb({x,++hi});
}
void del() { // delete from front
if (d.front().s == lo++) d.pop_front();
}
int get() {
return sz(d) ? d.front().f : INF;
}
};
int cnt(int i, int j){
int res = 0;
for (int x = 1; x <= N; x++){
if (presolve[x][j] - presolve[x][i - 1] == j - i + 1){
res += 1;
}
}
return res;
}
int score(int i, int j){
//value of one indexed [i, j] inclusive interval
int val = prefixpoints[j] - prefixpoints[i - 1];
int res = 0;
for (int x = 1; x <= N; x++){
if (presolve[x][j] - presolve[x][i - 1] == j - i + 1){
res += val;
}
}
return res;
}
void fill(int idx, int L, int R, int lo, int hi){
if (lo == hi){
for (int i = L; i <= R; i++){
ranges[idx][i] = lo;
}
return;
}
else{
int mid = (lo + hi)/2;
int k = cnt(mid, idx);
fill(idx, L, k, lo, mid);
fill(idx, k+1, R, mid + 1, hi);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> T >> S;
for (int i = 1; i <= T; i++){
cin >> points[i];
}
prefixpoints[0] = 0;
for (int i = 1; i <= T; i++){
prefixpoints[i] = prefixpoints[i - 1] + points[i];
}
for (int i = 1; i <= N; i++){
string s; cin >> s;
for (int j = 1; j <= T; j++){
solves[i][j] = (s[j - 1] - '0');
}
presolve[i][0] = 0;
for (int j = 1; j <= T; j++){
presolve[i][j] = solves[i][j] + presolve[i][j - 1];
}
}
for (int i = 1; i <= T; i++){
int bnd = cnt(i, i);
fill(i, 0, bnd, 1, i);
/*for (int j = 0; j <= bnd; j++){
int lo = 1;
int hi = i;
while (lo != hi){
int mid = (lo + hi)/2;
if (cnt(mid, i) < j){
lo = mid + 1;
}
else{
hi = mid;
}
}
ranges[i][j] = lo;
}*/
for (int j = bnd + 1; j <= N + 1; j++){
ranges[i][j] = INF;
}
}
for (int j = 1; j <= T; j++){
DP2[j] = score(1, j);
}
DP2[0] = INF;
cout << DP2[T] << endl;
for (int i = 2; i <= S; i++){
for (int j = 1; j <= T; j++){
DP1[j] = DP2[j];
}
for (int j = 0; j < i; j++){
DP2[j] = INF;
}
MinDeque M[N + 1];
for (int j = i; j <= T; j++){
for (int k = 0; k <= N; k++){
while (M[k].hi < min(j, ranges[j][k + 1] - 1) - 1){
M[k].ins(DP1[M[k].hi + 1] - k*prefixpoints[M[k].hi + 1]);
}
while (M[k].lo < min(j, ranges[j][k]) - 1){
M[k].del();
}
}
DP2[j] = INF;
for (int k = 0; k <= N; k++){
if (M[k].get() < INF){
//cout << i << ' ' << j << ' ' << M[k].get() << ' ' << M[k].lo << ' ' << M[k].hi << ' ' << k << endl;
DP2[j] = min(DP2[j], k*prefixpoints[j] + M[k].get());
}
}
//cout << i << ' ' << j << ' ' << DP2[j] << endl;
}
cout << DP2[T] << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
1188 KB |
Output is correct |
| 2 |
Correct |
43 ms |
1188 KB |
Output is correct |
| 3 |
Correct |
50 ms |
1288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
368 ms |
2112 KB |
Output is correct |
| 2 |
Correct |
625 ms |
2516 KB |
Output is correct |
| 3 |
Correct |
1047 ms |
3020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
732 KB |
Output is correct |
| 3 |
Correct |
47 ms |
1188 KB |
Output is correct |
| 4 |
Correct |
43 ms |
1188 KB |
Output is correct |
| 5 |
Correct |
50 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
368 ms |
2112 KB |
Output is correct |
| 7 |
Correct |
625 ms |
2516 KB |
Output is correct |
| 8 |
Correct |
1047 ms |
3020 KB |
Output is correct |
| 9 |
Execution timed out |
2060 ms |
4340 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
