Submission #866150

#	Time	Username	Problem	Language	Result	Execution time	Memory
866150		andrei_boaca	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	650 ms	109856 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")*/
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e18;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
bool comp(pll a, pll b)
{
    return a.second>b.second;
}
int S,D,mns,pls;
ll cap[2005][2005],nodes,dist[2005],from[2005],l[2005],r[2005],nr1[2005],nr0[2005],maxi[2005];
vector<ll> muchii[2005];
int use[2005];
int flow;
bool sub3;
ll k;
bool byplus(int a,int b)
{
    return cap[a][pls]>cap[b][pls];
}
long long find_maximum(int K, std::vector<std::vector<int>> vectoras)
{
    k=K;
	n = vectoras.size();
	m = vectoras[0].size();
	sol=vectoras;
    v=vectoras;
    sub3=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            sol[i][j]=-1;
            if(v[i][j]>1)
                sub3=0;
        }
    pls=0;
    mns=1;
    ll ans=0;
    multiset<pll> s;
    for(int i=0;i<n;i++)
    {
        l[i]=k-1;
        r[i]=m;
        cap[i][mns]=k;
        cap[i][pls]=0;
        for(int j=0;j<k;j++)
            ans-=v[i][j];
        s.insert({v[i][r[i]-1]+v[i][l[i]],i});
    }
    for(int pas=0;pas<k*n/2;pas++)
    {
        auto it=prev(s.end());
        int i=(*it).second;
        cap[i][mns]--;
        cap[i][pls]++;
        ans+=v[i][r[i]-1]+v[i][l[i]];
        r[i]--;
        l[i]--;
        s.erase(it);
        if(cap[i][mns]>0)
            s.insert({v[i][r[i]-1]+v[i][l[i]],i});
    }
    for(int i=0;i<n;i++)
    {
        l[i]=0;
        r[i]=m-1;
    }
    for(int pas=0;pas<k;pas++)
    {
        vector<int> linii;
        for(int i=0;i<n;i++)
            linii.push_back(i);
        sort(linii.begin(),linii.end(),byplus);
        for(int z=0;z<n;z++)
        {
            int i=linii[z];
            if(z<n/2)
            {
                assert(cap[i][pls]>0);
                cap[i][pls]--;
                sol[i][r[i]]=pas;
                r[i]--;
            }
            else
            {
                assert(cap[i][mns]>0);
                cap[i][mns]--;
                sol[i][l[i]]=pas;
                l[i]++;
            }
        }
    }
    allocate_tickets(sol);
	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