#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]; //ranges[j][k] is the min positive integer 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 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;
}
bool on[51]; //these all start as false
int val[51];
vector<int> entry[20005];
vector<int> back[20005];
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');
}
for (int j = 1; j <= T; j++){
if (solves[i][j] == true){
if (solves[i][j-1] == false){
entry[j].push_back(i);
}
if (solves[i][j+1] == false){
back[j].push_back(i);
}
}
}
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++){
vector<int> v;
for (int j: entry[i]){
on[j] = true;
val[j] = i;
}
for (int j = 1; j <= N; j++){
if (on[j]){
v.push_back(val[j]);
}
}
sort(v.begin(), v.end());
ranges[i][0] = 1;
for (int j = 1; j <= v.size(); j++){
ranges[i][j] = v[j - 1];
}
for (int j = v.size() + 1; j <= N + 1; j++){
ranges[i][j] = INF;
}
for (int j: back[i]){
on[j] = false;
}
}
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;
}
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j <= v.size(); j++){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2208 KB |
Output is correct |
| 2 |
Correct |
35 ms |
2208 KB |
Output is correct |
| 3 |
Correct |
36 ms |
2288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
161 ms |
3136 KB |
Output is correct |
| 2 |
Correct |
223 ms |
3568 KB |
Output is correct |
| 3 |
Correct |
255 ms |
3948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1640 KB |
Output is correct |
| 3 |
Correct |
39 ms |
2208 KB |
Output is correct |
| 4 |
Correct |
35 ms |
2208 KB |
Output is correct |
| 5 |
Correct |
36 ms |
2288 KB |
Output is correct |
| 6 |
Correct |
161 ms |
3136 KB |
Output is correct |
| 7 |
Correct |
223 ms |
3568 KB |
Output is correct |
| 8 |
Correct |
255 ms |
3948 KB |
Output is correct |
| 9 |
Correct |
365 ms |
5356 KB |
Output is correct |
| 10 |
Correct |
582 ms |
6508 KB |
Output is correct |
| 11 |
Correct |
1105 ms |
11260 KB |
Output is correct |
| 12 |
Correct |
1146 ms |
12648 KB |
Output is correct |
| 13 |
Correct |
1309 ms |
14040 KB |
Output is correct |
| 14 |
Correct |
1309 ms |
15236 KB |
Output is correct |
| 15 |
Correct |
1269 ms |
16224 KB |
Output is correct |
