#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
int dp[20005][55],rmq[55][16][20005],vals[20005],loga[20005];
int n,t,S;
int val[20005];
bool have[55][20005];
int nxt[55][20005],s[20005];
bool bad[55];
int mycost[55];
int need[20005][55];
bool add=1;
vector<pii> v[55];
int getmin(int st,int dr,int k)
{
int l=loga[dr-st+1];
int rez=min(rmq[k][l][st],rmq[k][l][dr-(1<<l)+1]);
if(add)
v[k].push_back({st,dr});
return rez;
}
vector<int> mypoz[20005];
bool comp(pii a, pii b)
{
return a.second>b.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>t>>S;
for(int i=1;i<=t;i++)
{
for(int j=0;j<=15;j++)
if((1LL<<j)<=i)
loga[i]=j;
}
for(int i=1;i<=t;i++)
{
cin>>val[i];
s[i]=s[i-1]+val[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)
{
char c;
cin>>c;
have[i][j]=c-'0';
}
for(int i=1;i<=n;i++)
{
nxt[i][0]=0;
for(int j=1;j<=t;j++)
{
nxt[i][j]=nxt[i][j-1];
if(!have[i][j])
nxt[i][j]=j;
}
/*for(int j=1;j<=t;j++)
cout<<nxt[i][j]<<' ';
cout<<'\n';*/
}
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
mypoz[i].push_back(nxt[j][i]);
sort(mypoz[i].begin(),mypoz[i].end());
reverse(mypoz[i].begin(),mypoz[i].end());
}
dp[0][0]=0;
for(int i=1;i<=S;i++)
dp[0][i]=2e9;
for(int i=1;i<=t;i++)
dp[i][0]=2e9;
for(int k=0;k<=n;k++)
{
for(int i=0;i<=t;i++)
vals[i]=dp[i][0]-k*s[i];
for(int i=t;i>=0;i--)
{
rmq[k][0][i]=vals[i];
for(int j=1;j<=15;j++)
{
int poz=i+(1LL<<(j-1))-1;
if(poz>t)
break;
rmq[k][j][i]=rmq[k][j-1][i];
if(poz+1<=t)
rmq[k][j][i]=min(rmq[k][j][i],rmq[k][j-1][poz+1]);
}
}
}
for(int a=1;a<=S;a++)
{
for(int i=1;i<=t;i++)
{
dp[i][a]=2e9;
/*for(int k=i-1;k>=0;k--)
dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);*/
}
for(int i=1;i<=t;i++)
{
dp[i][a]=2e9;
int cnt=n;
int cur=i;
for(int j=0;j<mypoz[i].size();j++)
{
int poz=mypoz[i][j];
int st=poz;
int dr=cur-1;
if(st<=dr)
{
int nr=getmin(st,dr,cnt)+cnt*s[i];
dp[i][a]=min(dp[i][a],nr);
}
cur=poz;
cnt--;
}
int st=0;
int dr=cur-1;
if(st<=dr)
{
int nr=getmin(st,dr,cnt)+cnt*s[i];
dp[i][a]=min(dp[i][a],nr);
}
}
for(int k=0;k<=n;k++)
{
if(add)
{
sort(v[k].begin(),v[k].end(),comp);
int poz=t;
for(pii a:v[k])
{
int st=a.first,dr=a.second;
while(poz>=st)
{
need[poz][k]=dr;
poz--;
}
}
}
for(int i=0;i<=t;i++)
vals[i]=dp[i][a]-k*s[i];
for(int i=t;i>=0;i--)
{
rmq[k][0][i]=vals[i];
for(int j=1;j<=loga[need[i][k]-i+1]+1;j++)
{
int poz=i+(1LL<<(j-1))-1;
if(poz>t)
break;
rmq[k][j][i]=rmq[k][j-1][i];
if(poz+1<=t)
rmq[k][j][i]=min(rmq[k][j][i],rmq[k][j-1][poz+1]);
}
}
}
add=0;
}
for(int i=1;i<=S;i++)
cout<<dp[t][i]<<'\n';
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int j=0;j<mypoz[i].size();j++)
| ~^~~~~~~~~~~~~~~~
popeala.cpp:37:23: warning: array subscript 32768 is above array bounds of 'int [20005]' [-Warray-bounds]
37 | loga[i]=j;
| ~~~~~~^
popeala.cpp:5:50: note: while referencing 'loga'
5 | int dp[20005][55],rmq[55][16][20005],vals[20005],loga[20005];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
23 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
26 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
11460 KB |
Output is correct |
| 2 |
Correct |
193 ms |
15180 KB |
Output is correct |
| 3 |
Correct |
227 ms |
19140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
23 ms |
4820 KB |
Output is correct |
| 5 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
117 ms |
11460 KB |
Output is correct |
| 7 |
Correct |
193 ms |
15180 KB |
Output is correct |
| 8 |
Correct |
227 ms |
19140 KB |
Output is correct |
| 9 |
Correct |
368 ms |
29772 KB |
Output is correct |
| 10 |
Correct |
561 ms |
38092 KB |
Output is correct |
| 11 |
Correct |
1224 ms |
85028 KB |
Output is correct |
| 12 |
Correct |
1270 ms |
87868 KB |
Output is correct |
| 13 |
Correct |
1416 ms |
86316 KB |
Output is correct |
| 14 |
Correct |
1450 ms |
86488 KB |
Output is correct |
| 15 |
Correct |
1494 ms |
86616 KB |
Output is correct |
