| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 874881 | 2023-11-18T03:17:20 Z | Faisal_Saqib | Popeala (CEOI16_popeala) | C++17 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <algorithm>For test cases worth 8 points, T ≤ 40.
For test cases worth another 9 points, 40 < T ≤ 500.
using namespace std;
#define int long long
const int T=2e4+10;
const int N=52;
const int inf=1e18;
int points[T];
int pre[T];
vector<int> zero[N];
string results[N];
int dp[T][N];
signed main()
{
int n,t,s;
cin>>n>>t>>s;
for(int i=0;i<t;i++)
{
cin>>points[i];
pre[i+1]=pre[i]+points[i];
}
for(int i=0;i<n;i++)
{
cin>>results[i];
for(int j=0;j<t;j++)
if(results[i][j]=='0')
zero[i].push_back(j);
}
for(int i=0;i<=t;i++)
for(int j=0;j<=s;j++)
dp[i][j]=inf;
// dp[i][j] we spilt the first i testcases into j subtask
dp[0][0]=0;
// dp[i][j] ---> dp[i+1..n][j+1]
for(int i=0;i<t;i++)
{
for(int j=0;j<s;j++)
{
if(dp[i][j]==inf)
continue;
for(int new_i=i+1;new_i<=t;new_i++)
{
int cur=pre[new_i]-pre[i];
int score=n*cur;
for(int participant=0;participant<n;participant++)
{
auto it=lower_bound(begin(zero[participant]),end(zero[participant]),i);
if(it!=end(zero[participant]) and *it < new_i)
score-=cur;
}
dp[new_i][j+1]=min(dp[new_i][j+1],dp[i][j]+score);
// cout<<"For" <<new_i<<' '<<j+1<<' '<<dp[new_i][j+1]<<endl;
}
}
}
for(int j=1;j<=s;j++)
cout<<dp[t][j]<<'\n';
return 0;
}