| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 592408 | ogibogi2004 | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long find_maximum(ll k, vector<vector<ll>> x) {
//cout<<"?\n";
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> answer;
vector<ll>smallest[n];
for(ll i=0;i<n;i++)
{
smallest[i]=x[i];
sort(smallest[i].begin(),smallest[i].end());
}
ll use[n][m];
memset(use,-1,sizeof(use));
ll dp[n][n*k];
ll hist[n][n*k];
bool c[n][n*k];
memset(c,0,sizeof(c));
ll sum=0;
for(ll j=0;j<k;j++)sum-=smallest[0][j];
dp[0][k]=sum;c[0][k]=1;
hist[0][k]=k;
for(ll j=k-1;j>=0;j--)
{
sum+=smallest[0][j];
sum+=smallest[0][smallest[0].size()-(k-j)];
dp[0][j]=sum;c[0][j]=1;
hist[0][j]=j;
}
//cout<<"eho1\n";
for(ll i=1;i<n;i++)
{
sum=0;
for(ll j=0;j<k;j++)sum-=smallest[i][j];
for(ll prv=0;prv+k<=n*k/2;prv++)
{
if(!c[i-1][prv])continue;
if(c[i][prv+k]==0)
{
dp[i][prv+k]=dp[i-1][prv]+sum;
c[i][prv+k]=1;
hist[i][prv+k]=k;
}
else
{
if(dp[i-1][prv]+sum>dp[i][prv+k])
{
dp[i][prv+k]=dp[i-1][prv]+sum;
hist[i][prv+k]=k;
}
}
}
for(ll j=k-1;j>=0;j--)
{
sum+=smallest[i][j];
sum+=smallest[i][smallest[i].size()-(k-j)];
for(ll prv=0;prv+j<=n*k/2;prv++)
{
if(!c[i-1][prv])continue;
if(c[i][prv+j]==0)
{
dp[i][prv+j]=dp[i-1][prv]+sum;
hist[i][prv+j]=j;
c[i][prv+j]=1;
}
else
{
if(dp[i-1][prv]+sum>dp[i][prv+j])
{
dp[i][prv+j]=dp[i-1][prv]+sum;
hist[i][prv+j]=j;
}
}
}
}
}
//cout<<"eho2\n";
ll t=n*k/2;
vector<ll>small[n];
vector<ll>large[n];
for(ll j=n-1;j>=0;j--)
{
//cout<<j<<" "<<t<<endl;
ll cnts=hist[j][t];
//cout<<" "<<cnts<<endl;
vector<pair<ll,ll> >smallest1;
for(ll i=0;i<m;i++)
{
smallest1.push_back({x[j][i],i});
}
sort(smallest1.begin(),smallest1.end());
for(ll i=0;i<cnts;i++)
{
small[j].push_back(smallest1[i].second);
}
for(ll i=1;i<=k-cnts;i++)
{
large[j].push_back(smallest1[m-i].second);
}
t-=cnts;
}
//cout<<"eho3\n";
//cout<<dp[n-1][n*k/2]<<endl;
for(ll j=0;j<k;j++)
{
//cout<<j<<endl;
vector<pair<ll,ll> >sizes;
for(ll i=0;i<n;i++)
{
sizes.push_back({small[i].size(),i});
}
sort(sizes.rbegin(),sizes.rend());
for(ll i=0;i<sizes.size();i++)
{
//cout<< " "<<i<<endl;
if(i<n/2)
{
//cout<<" "<<small[sizes[i].second].size()<<endl;
use[sizes[i].second][small[sizes[i].second].back()]=j;
small[sizes[i].second].pop_back();
}
else
{
use[sizes[i].second][large[sizes[i].second].back()]=j;
large[sizes[i].second].pop_back();
}
}
}
//cout<<"eho4\n";
for(ll i=0;i<n;i++)
{
//cout<<i<<endl;
vector<int>v;
for(ll j=0;j<m;j++)
{
v.push_back(use[i][j]);
}
answer.push_back(v);
}
allocate_tickets(answer);
return dp[n-1][n*k/2];
}
/*
2 3 2
0 2 5
1 1 3
*/