Submission #615968

#	Time	Username	Problem	Language	Result	Execution time	Memory
615968		azberjibiou	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	746 ms	99624 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int mxN=2000;
int N, M;
vector <vector <int>> col;
ll ans;
int maxi[mxN][mxN], mini[mxN][mxN];
int cur[mxN];
int lc[mxN], rc[mxN];
priority_queue <pii> pq;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
    N=x.size();
    M=x[0].size();
	col.resize(N);
	for(int i=0;i<N;i++)    col[i].resize(M);
	for(int i=0;i<N;i++)    for(int j=0;j<M;j++)    col[i][j]=-1;
	for(int i=0;i<N;i++)
    {
        for(int j=0;j<k;j++)    maxi[i][j]=x[i][j+M-k];
        for(int j=0;j<k;j++)    mini[i][j]=x[i][j], ans-=x[i][j];
    }
    for(int i=0;i<N;i++)    cur[i]=k-1;
    for(int i=0;i<N;i++)    pq.emplace(maxi[i][k-1]+mini[i][k-1], i);
    for(int i=0;i<k*N/2;i++)
    {
        pii now=pq.top();
        pq.pop();
        ans+=now.fir;
        cur[now.sec]--;
        if(cur[now.sec]!=-1)
        {
            pq.emplace(maxi[now.sec][cur[now.sec]]+mini[now.sec][cur[now.sec]], now.sec);
        }
    }
    for(int i=0;i<N;i++)    lc[i]=0, rc[i]=M-1;
    vector <pii> tmp1;
    tmp1.resize(N);
    for(int i=0;i<N;i++)    tmp1[i]=pii(cur[i], i);
    for(int i=0;i<k;i++)
    {
        sort(tmp1.begin(), tmp1.end());
        for(int j=0;j<N/2;j++)  col[tmp1[j].sec][rc[tmp1[j].sec]--]=i;
        for(int j=N/2;j<N;j++)  col[tmp1[j].sec][lc[tmp1[j].sec]++]=i, tmp1[j].fir--;
    }
	allocate_tickets(col);
	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