Submission #549421

#	Time	Username	Problem	Language	Result	Execution time	Memory
549421		Bench0310	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	833 ms	84044 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;
typedef long long ll;

ll find_maximum(int k,vector<vector<int>> x)
{
    int n=x.size();
    int m=x[0].size();
    ll score=0;
    vector<int> ones(n,k);
    vector<array<int,2>> v;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k;j++)
        {
            score+=x[i][m-1-j];
            v.push_back({x[i][j]+x[i][m-k+j],i});
        }
    }
    sort(v.begin(),v.end());
    for(int j=0;j<n*k/2;j++)
    {
        auto [a,i]=v[j];
        score-=a;
        ones[i]--;
    }
    vector res(n,vector(m,int(-1)));
    int p=0;
    for(int i=0;i<n;i++)    
    {
        for(int j=m-ones[i];j<m;j++)
        {
            res[i][j]=p;
            p=(p+1)%k;
        }
        int r=p;
        for(int j=0;j<k-ones[i];j++) res[i][j]=(r+j)%k;
    }
    allocate_tickets(res);
    return score;
}

//int main()
//{
//    
//    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