Submission #1063022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063022		TlenekWodoru	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	735 ms	105988 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
int k,n,m,n2;
vector<vector<int>>answer;
vector<vector<pair<int,int>>>Tab;
int miejsce[1509];
vector<int>V1[1509],V2[1509];
int CzyWziete[1509];
long long find_maximum(int K, vector<vector<int>>A)
{
    k=K;
    n = A.size();
    n2=n/2;
    m = A[0].size();
    answer.resize(n,vector<int>(m,-1));
    for(int i=0;i<n;i++)
    {
        vector<pair<int,int>>Temp;
        for(int j=0;j<m;j++)
        {
            Temp.push_back({A[i][j],j});
        }
        sort(Temp.begin(),Temp.end());
        Tab.push_back(Temp);
    }
    long long wynik=0;
    const int kij=m-k;
    for(int i=0;i<n;i++)
    {
        for(int j=kij;j<m;j++)
        {
            wynik+=Tab[i][j].first;
        }
    }
    set<pair<int,int>>S;
    for(int i=0;i<n;i++)
    {
        miejsce[i]=0;
        S.insert({Tab[i][0].first+Tab[i][kij].first,i});
    }
    for(int I=1;I<=n*k/2;I++)
    {
        pair<int,int>xd=*S.begin();
        S.erase(xd);
        wynik-=xd.first;
        miejsce[xd.second]++;
        if(miejsce[xd.second]+kij<m)
        {
            S.insert({Tab[xd.second][miejsce[xd.second]].first+Tab[xd.second][miejsce[xd.second]+kij].first,xd.second});
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<miejsce[i];j++)
        {
            V1[i].push_back(Tab[i][j].second);
        }
        for(int j=miejsce[i]+kij;j<m;j++)
        {
            V2[i].push_back(Tab[i][j].second);
        }
    }
    memset(CzyWziete,-1,sizeof(CzyWziete));
    for(int i=0;i<k;i++)
    {
        int IleMalych=n2;
        for(int j=0;j<n;j++)
        {
            if((int)V1[j].size()==0)
            {
                answer[j][V2[j].back()]=i;
                V2[j].pop_back();
                CzyWziete[j]=i;
            }
            else if((int)V2[j].size()==0)
            {
                answer[j][V1[j].back()]=i;
                V1[j].pop_back();
                CzyWziete[j]=i;
                IleMalych--;
            }
        }
        for(int j=0;j<n;j++)
        {
            if(CzyWziete[j]==i){continue;}
            if(IleMalych>0)
            {
                answer[j][V1[j].back()]=i;
                V1[j].pop_back();
                IleMalych--;
            }
            else
            {
                answer[j][V2[j].back()]=i;
                V2[j].pop_back();
            }
        }
    }
    allocate_tickets(answer);
    return wynik;
}

• 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