#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 min1[55],min2[55],min3[55];
void putin(int val,int nr)
{
if(val<min1[nr])
{
min3[nr]=min2[nr];
min2[nr]=min1[nr];
min1[nr]=val;
return;
}
if(val<min2[nr])
{
min3[nr]=min2[nr];
min2[nr]=val;
return;
}
if(val<min3[nr])
{
min3[nr]=val;
return;
}
}
void putout(int val,int nr)
{
if(val==min1[nr])
{
min1[nr]=min2[nr];
min2[nr]=min3[nr];
min3[nr]=2e9;
return;
}
if(val==min2[nr])
{
min2[nr]=min3[nr];
min3[nr]=2e9;
return;
}
if(val==min3[nr])
{
min3[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();
min1[i]=min2[i]=min3[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);
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=min1[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:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int j=0;j<vals.size();j++)
| ~^~~~~~~~~~~~
popeala.cpp:149:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | while(p[nr]<events[nr].size()&&events[nr][p[nr]].poz<=i)
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
126 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
120 ms |
1596 KB |
Output is correct |
| 3 |
Correct |
125 ms |
1492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
601 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
126 ms |
1620 KB |
Output is correct |
| 4 |
Correct |
120 ms |
1596 KB |
Output is correct |
| 5 |
Correct |
125 ms |
1492 KB |
Output is correct |
| 6 |
Incorrect |
601 ms |
4180 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
