Submission #304878

#	Time	Username	Problem	Language	Result	Execution time	Memory
304878		daniel920712	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	2881 ms	216368 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
using namespace std;
struct A
{
    int where;
    int con1,con2;
}tt[1505];
priority_queue < pair < pair < long long ,int > , pair < int , int > > , vector < pair < pair < long long ,int > , pair < int , int > > > , less < pair < pair < long long ,int > , pair < int , int > > > > xx,yy;
vector < vector < int > > answer;
vector < int > row;
vector< vector<int> >  all;
vector < pair < int , pair < int , int > > > how;
vector < int > uu2[1505];
set < int > uu[1505];
bool have[1505][1505];
bool have2[305][90005];
bool use[1505]={0};
long long DP[1505][1505];
long long DP2[305][90005];
long long con[1505][1505];
int a[1505];
int b[1505];
int N,M;


long long find_maximum(int k,vector< vector<int> > x)
{
    long long ans=0;
    int i,j,ll,rr;
    pair < pair < long long ,int > , pair < int , int > > aa,bb;
    N=x.size();
    M=x[0].size();
    for(i=0;i<N/2;i++)
    {
        for(j=0;j<k;j++)
        {
            ans-=x[i][j];
            uu[i].insert(j);
        }
        xx.push(make_pair(make_pair(x[i][k-1]+x[i][M-1],i),make_pair(k-1,M-1)));
    }
    for(i=N/2;i<N;i++)
    {
        for(j=0;j<k;j++)
        {
            ans+=x[i][M-j-1];
            uu[i].insert(M-j-1);
        }
        yy.push(make_pair(make_pair(0-x[i][M-k]-x[i][0],i),make_pair(M-k,0)));
    }
    for(i=0;i<M;i++) row.push_back(-1);
    for(i=0;i<N;i++) answer.push_back(row);
    //printf("%lld\n",ans);
    while(1)
    {
        if(xx.empty()||yy.empty()) break;
        aa=xx.top();
        bb=yy.top();
        xx.pop();
        yy.pop();
        if(aa.first.first+bb.first.first>0)
        {
            ans+=aa.first.first+bb.first.first;
            //printf("%lld\n",ans);
            uu[aa.first.second].erase(aa.second.first);
            uu[aa.first.second].insert(aa.second.second);
            aa.second.first--;
            aa.second.second--;
            if(aa.second.first>=0)
            {
                aa.first.first=x[aa.first.second][aa.second.first]+x[aa.first.second][aa.second.second];
                xx.push(aa);
            }

            uu[bb.first.second].erase(bb.second.first);
            uu[bb.first.second].insert(bb.second.second);
            bb.second.first++;
            bb.second.second++;
            if(bb.second.first<M)
            {
                bb.first.first=0-x[bb.first.second][bb.second.first]-x[bb.first.second][bb.second.second];
                yy.push(bb);
            }

        }
        else break;

    }
    for(i=0;i<N;i++)
    {
        for(auto j:uu[i])
        {
            how.push_back(make_pair(x[i][j],make_pair(i,j)));
            uu2[i].push_back(j);
        }
    }
    sort(how.begin(),how.end());
    for(i=0;i<N*k;i++) con[how[i].second.first][how[i].second.second]=i;
    for(i=0;i<N;i++)
    {
        a[i]=0;
        b[i]=k-1;
    }
    for(i=0;i<k;i++)
    {
        ll=0;
        rr=0;
        for(j=0;j<N;j++) use[j]=0;
        for(j=0;j<N;j++)
        {
            if(a[j]<k&&con[j][uu2[j][a[j]]]>=N*k/2)
            {
                use[j]=1;
                rr++;
                answer[j][uu2[j][b[j]]]=i;
                b[j]--;
            }
            if(b[j]>=0&&con[j][uu2[j][b[j]]]<N*k/2)
            {
                use[j]=1;
                ll++;
                answer[j][uu2[j][a[j]]]=i;
                a[j]++;
            }
        }

        for(j=0;j<N;j++)
        {
            if(use[j]) continue;
            if(ll<N/2)
            {
                use[j]=1;
                ll++;
                answer[j][uu2[j][a[j]]]=i;
                a[j]++;
            }
            else
            {
                use[j]=1;
                rr++;
                answer[j][uu2[j][b[j]]]=i;
                b[j]--;
            }
        }
    }
	allocate_tickets(answer);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10