Submission #318549

#	Time	Username	Problem	Language	Result	Execution time	Memory
318549		giorgigagua2006	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	947 ms	54500 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
long long i,j,n,m,res;
long long find_maximum(int k, std::vector<std::vector<int>> x) 
{
	n=x.size();
	m=x[0].size();
    vector<vector<int>>answer(n,vector<int>(m,-1));
    vector<int>v(n,0);
    set<pair<long long,int>>s;
    for(int i=0;i<n;i++)
	{
        for(int j=m-k;j<m;j++)
		res+=x[i][j];
        s.insert({x[i][0]+x[i][m-k],i});
    }
    for(j=0;j<k*n/2;j++){
        auto p=*s.begin();
        int val=p.first;
        i=p.second;
        res-=val;
        s.erase(*s.begin());
        v[i]++;
        int a=v[i];
        if(a<k)
		s.insert(make_pair(x[i][a]+x[i][m-k+a],i));
    }
    int r=0;
    for(i=0;i<n;i++)
	{
        for(j=0;j<v[i];j++)
		{
            answer[i][j]=r;
            r++;
            r%=k;
        }
        int rr=r;
        for(j=m-k+v[i];j<m;j++)
		{
            answer[i][j]=rr;
            rr++;
            rr%=k;
        }
    }
    allocate_tickets(answer);
    return res;
}

• 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