#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
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 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]);
return rez;
}
vector<int> mypoz[20005];
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++)
{
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<=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 i=1;i<=S;i++)
cout<<dp[t][i]<<'\n';
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j=0;j<mypoz[i].size();j++)
| ~^~~~~~~~~~~~~~~~
popeala.cpp:27:23: warning: array subscript 32768 is above array bounds of 'int [20005]' [-Warray-bounds]
27 | loga[i]=j;
| ~~~~~~^
popeala.cpp:4:50: note: while referencing 'loga'
4 | 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 |
3 ms |
2132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
4564 KB |
Output is correct |
| 2 |
Correct |
37 ms |
4520 KB |
Output is correct |
| 3 |
Correct |
34 ms |
4648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
10076 KB |
Output is correct |
| 2 |
Correct |
272 ms |
13180 KB |
Output is correct |
| 3 |
Correct |
372 ms |
16496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 3 |
Correct |
34 ms |
4564 KB |
Output is correct |
| 4 |
Correct |
37 ms |
4520 KB |
Output is correct |
| 5 |
Correct |
34 ms |
4648 KB |
Output is correct |
| 6 |
Correct |
194 ms |
10076 KB |
Output is correct |
| 7 |
Correct |
272 ms |
13180 KB |
Output is correct |
| 8 |
Correct |
372 ms |
16496 KB |
Output is correct |
| 9 |
Correct |
712 ms |
25556 KB |
Output is correct |
| 10 |
Correct |
871 ms |
32852 KB |
Output is correct |
| 11 |
Execution timed out |
2083 ms |
71672 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
