Submission #337677

#	Time	Username	Problem	Language	Result	Execution time	Memory
337677		MvC	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1582 ms	119028 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e3+50;
const ll mod=1e9+7;
using namespace std;
int n,m,i,j,nr,vz[nmax],t,l[nmax],r[nmax];
vector<vector<int> >rs;
vector<pair<int,pair<int,int> > >vc;
vector<int>v[2][nmax];
vector<pair<int,int> >ea,eb,fft;
set<pair<int,int> >s,b,st;
pair<int,int>pr;
set<pair<int,int> >::iterator it;
ll sm;
ll find_maximum(int k,vector<vector<int> > a)
{
    n=lun(a),m=lun(a[0]);
    for(i=0;i<n;i++)
    {
        l[i]=k-1;
        r[i]=m-1;
        st.in(mkp(a[i][l[i]]+a[i][r[i]],i));
    }
    for(i=0;i<n*k/2;i++)
    {
        pr=*(--st.end());
        st.er(--st.end());
        r[pr.sc]--,l[pr.sc]--;
        if(l[pr.sc]>-1)st.in(mkp(a[pr.sc][l[pr.sc]]+a[pr.sc][r[pr.sc]],pr.sc));
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<=l[i];j++)vc.pb(mkp(a[i][j],mkp(i,j)));
        for(j=r[i]+1;j<m;j++)vc.pb(mkp(a[i][j],mkp(i,j)));
    }
    sort(all(vc));
    for(i=0;i<n*k;i++)
    {
        v[i<n*k/2][vc[i].sc.fr].pb(vc[i].sc.sc);
        if(i<n*k/2)sm-=1LL*vc[i].fr;
        else sm+=1LL*vc[i].fr;
    }
    for(i=0;i<n;i++)
    {
        if(!v[1][i].empty())s.in(mkp(lun(v[1][i]),i));
    }
    rs.resize(n);
    for(i=0;i<n;i++)for(j=0;j<m;j++)rs[i].pb(-1);
    for(i=0;i<k;i++)
    {
        ea.clear();
        it=--s.end();
        for(j=0;j<n/2;j++)
        {
            t=it->sc;
            rs[t][v[1][t].back()]=i;
            v[1][t].pop_back();
            vz[t]=1;
            ea.pb(*it);
            it--;
        }
        for(j=0;j<n;j++)
        {
            if(!vz[j])
            {
                rs[j][v[0][j].back()]=i;
                v[0][j].pop_back();
            }
            vz[j]=0;
        }
        for(j=0;j<lun(ea);j++)
        {
            s.er(s.fd(ea[j]));
            if(ea[j].fr>1)s.in(mkp(ea[j].fr-1,ea[j].sc));
        }
    }
    allocate_tickets(rs);
    return sm;
}
/*int main()
{
    //freopen("sol.in","r",stdin);
    //freopen("sol.out","w",stdout);
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 0;
}*/

• 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