#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=2e9+1,N=5e4+1;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
vector<LineContainer> sg(N*4);
void update(int i,int l,int r,int index, int slope,int yin){
if(index<l||r<index) return ;
sg[i].add(slope,yin);
if(l!=r){
update(i*2,l,(r+l)/2,index,slope,yin);
update(i*2+1,(r+l)/2+1,r,index,slope,yin);
}
return ;
}
int query(int i,int l,int r, int ql ,int qr,int point){
if(qr<l||r<ql||sg[i].empty()) return -inf;
if(ql<=l&&r<=qr){
return sg[i].query(point);
}
return max(query(i*2,l,(r+l)/2,ql,qr,point),query(i*2+1,(r+l)/2+1,r,ql,qr,point));
}
signed main(){
freopen("in.txt","r",stdin);
int n,t,s;
cin>>n>>t>>s;
vector<vector<int>> dp(s+1,vector<int>(t+1,inf));
for(int i=0;i<t;i++) dp[0][i]=0;
vector<int> v(t);
for(int&x:v) cin>>x;
vector<int> prefix=v;
for(int i=1;i<t;i++) prefix[i]+=prefix[i-1];
vector<vector<char>> a(n,vector<char>(t));
for(int i=0;i<n;i++)
for(int j=0;j<t;j++)
cin>>a[i][j];
vector<vector<int>> last(n,vector<int>(t,-1));
for(int i=0;i<n;i++){
for(int j=0;j<t;j++){
if(a[i][j]=='0') last[i][j]=j;
else if(j) last[i][j]=last[i][j-1];
}
}
for(int subs=1;subs<=s;++subs){
for(int testcase=0;testcase<t;testcase++){
vector<int> pl;
for(int contestant=0;contestant<n;contestant++) pl.push_back(last[contestant][testcase]);
sort(pl.begin(),pl.end());
int cnt=0;
for(int&x:pl) cnt+=(x==-1) ;
if(subs==1)
dp[subs][testcase]=prefix[testcase]*cnt;
else{
if(testcase) dp[subs][testcase]=dp[subs-1][testcase-1]+v[testcase]*n;
}
if(subs==1) continue ;
for(int i=0;i<pl.size();i++){
if(pl[i]==-1) continue;
int da=-query(1,0,t,0,pl[i]-1,i);
if(pl[i]) dp[subs][testcase]=min(dp[subs][testcase],da+prefix[testcase]*i);
else{
if(subs==1) dp[subs][testcase]=min(dp[subs][testcase],prefix[testcase]*i);
}
}
}
for(int i=0;i<t*4;i++) sg[i].clear();
for(int testcase=0;testcase<t;testcase++){
update(1,0,t,testcase,prefix[testcase],-dp[subs][testcase]);
}
}
for(int i=1;i<=s;i++) cout<<dp[i][t-1]<<endl;
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<pl.size();i++){
| ~^~~~~~~~~~
popeala.cpp:54:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
13012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
13012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
13140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
13012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
