Submission #1274935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274935		lamlamlam	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	455 ms	54336 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#define ll long long
#define pii pair<int,int>
using namespace std;
struct Data{
    int l,r,id;
    bool operator < (const Data &o) const {
        if(l!=o.l) return l < o.l;
        return r < o.r;
    }
};
const int MN = 1505;
int N,M,st[MN],en[MN],h[MN],hh[MN];
ll ans;
bool vis[MN];
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n);
	priority_queue<pii> pq;
	for(int i=0; i<n; i++) en[i] = m-1, st[i]=k-1, h[i] = m-1, answer[i].resize(m);
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) answer[i][j] = -1;
	for(int i=0; i<n; i++){
        for(int j=0; j<k; j++) ans -= x[i][j], answer[i][j] = 1;
        pq.push({x[i][st[i]]+x[i][en[i]],i});
	}
	for (int t = 0; t < k*n/2; t++) {
		auto tmp = pq.top(); pq.pop();
		int i = tmp.second, val = tmp.first;
		ans += val;
        answer[i][st[i]] = -1;
        answer[i][en[i]] = 1;
        st[i]--; en[i]--;
        if(st[i]==-1) continue;
        pq.push({x[i][st[i]]+x[i][en[i]],i});
	}
	for(int t=0; t<k; t++){
        vector<pii> v(n);
        for(int i=0; i<n; i++){
            vis[i] = 0;
            v[i] = {-(h[i]-en[i]),i};
//            cerr << "PUSHING: " << i << ' ' << h[i] << ' ' << en[i] << ' ' << -(h[i]-en[i]) << endl;
        }
        sort(v.begin(),v.end());
        for(int i=0; i<n; i++){
            int id = v[i].second;
            if(i<n/2){
                answer[id][h[id]] = t;
                h[id]--;
            }
            else{
                answer[id][hh[id]] = t;
                hh[id]++;
            }
        }
	}
	allocate_tickets(answer);
	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