Submission #457574

#	Time	Username	Problem	Language	Result	Execution time	Memory
457574		vector	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1249 ms	92716 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define SIZE 1501
using namespace std;
typedef long long ll;
priority_queue<pair<ll, pair<int, int> > > q;
int l[SIZE], r[SIZE];
pair<int, int> arr[SIZE];
ll find_maximum(int K, vector<vector<int> > x)
{
	int N=x.size(), M=x[0].size(), col, num, id;
	ll sum=0, val;
	vector<vector<int> > ret(N);
	for (int i=0; i<N; i++) ret[i].resize(M);
	for (int i=0; i<N; i++) for (int j=0; j<M; j++) ret[i][j]=-1;
	for (int i=0; i<N; i++) for (int j=0; j<K; j++) {
        ret[i][j]=0, sum-=x[i][j];
        q.push(make_pair(x[i][j]+x[i][M+j-K], make_pair(i, j)));
	}
	for (int i=0; i<N*K/2; i++) {
        val=q.top().first, col=q.top().second.first, num=q.top().second.second;
        q.pop();
        ret[col][num]=-1, ret[col][M+num-K]=1, sum+=val;
	}
	for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (ret[i][j]==1) r[i]=M-1, arr[i].first++;
            else if (ret[i][j]==0) l[i]=0;
        }
        arr[i].second=i;
	}
	for (int i=0; i<K; i++) {
        sort(arr, arr+N);
        for (int j=0; j<N; j++) {
            id=arr[j].second;
            if (j<N/2) ret[id][l[id]++]=i;
            else ret[id][r[id]--]=i, arr[j].first--;
        }
	}
	allocate_tickets(ret);
    return sum;
}

• 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