#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
int dp[20005][55];
int n,t,S;
int val[20005];
bool have[55][20005];
int nxt[55][20005],s[20005];
bool bad[55];
int mycost[55];
struct ev
{
bool add;
int poz,val;
};
vector<ev> events[55];
bool comp(ev a, ev b)
{
return a.poz<b.poz;
}
int mini[55][55];
void putin(int val,int nr)
{
for(int i=1;i<=50;i++)
if(val<=mini[i][nr])
{
for(int j=50;j>i;j--)
mini[j][nr]=mini[j-1][nr];
mini[i][nr]=val;
return;
}
}
void putout(int val,int nr)
{
for(int i=1;i<=50;i++)
if(val==mini[i][nr])
{
for(int j=i+1;j<=50;j++)
mini[j-1][nr]=mini[j][nr];
mini[50][nr]=2e9;
return;
}
}
int p[55];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>t>>S;
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][t+1]=t+1;
for(int j=t;j>=1;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';*/
}
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 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=0;i<=n;i++)
{
events[i].clear();
for(int j=1;j<=50;j++)
mini[j][i]=2e9;
p[i]=0;
}
for(int i=1;i<=t;i++)
{
vector<int> vals;
for(int j=1;j<=n;j++)
vals.push_back(nxt[j][i]);
sort(vals.begin(),vals.end());
int nr=dp[i-1][a-1]-s[i-1]*n;
int cnt=n;
int cur=i;
for(int j=0;j<vals.size();j++)
{
int poz=vals[j];
int st=cur;
int dr=poz-1;
if(st<=dr)
{
events[cnt].push_back({1,st,nr});
events[cnt].push_back({0,dr+1,nr});
}
cur=poz;
cnt--;
nr+=s[i-1];
}
if(cur<=t)
{
events[cnt].push_back({1,cur,nr});
events[cnt].push_back({0,t+1,nr});
}
}
for(int i=0;i<=n;i++)
sort(events[i].begin(),events[i].end(),comp);
bool ok=0;
if(a==3)
ok=1;
for(int i=1;i<=t;i++)
{
for(int nr=0;nr<=n;nr++)
{
while(p[nr]<events[nr].size()&&events[nr][p[nr]].poz<=i)
{
int val=events[nr][p[nr]].val;
bool add=events[nr][p[nr]].add;
if(add)
putin(val,nr);
else
putout(val,nr);
p[nr]++;
}
int x=mini[1][nr];
x+=nr*s[i];
dp[i][a]=min(dp[i][a],x);
}
}
}
for(int i=1;i<=S;i++)
cout<<dp[t][i]<<'\n';
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j=0;j<vals.size();j++)
| ~^~~~~~~~~~~~
popeala.cpp:133:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while(p[nr]<events[nr].size()&&events[nr][p[nr]].poz<=i)
| ~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:126:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
126 | bool ok=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
224 ms |
1632 KB |
Output is correct |
| 3 |
Correct |
229 ms |
1636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
956 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
592 KB |
Output is correct |
| 3 |
Correct |
209 ms |
1620 KB |
Output is correct |
| 4 |
Correct |
224 ms |
1632 KB |
Output is correct |
| 5 |
Correct |
229 ms |
1636 KB |
Output is correct |
| 6 |
Incorrect |
956 ms |
4308 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
