Submission #1274744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274744		lamlamlam	Carnival Tickets (IOI20_tickets)	C++20	11 / 100	2 ms	836 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#define ll long long
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];
ll ams=0;
ll sol_ans(vector<Data> x){
    priority_queue<int> pq;
    int sz = x.size();
    ll best_ans = 0, cur = 0;
    for(int i=0; i<sz; i++) {
        if(i<sz/2) cur -= x[i].l, pq.push(x[i].r+x[i].l);
        else cur += x[i].r;
    }
    best_ans = cur;
    for(int i=sz/2; i<sz; i++){
        cur += - x[i].l - x[i].r;
        pq.push(x[i].r+x[i].l);
        cur += pq.top(); pq.pop();
        best_ans = max(best_ans,cur);
    }
    return best_ans;
}
void debug(vector<int> v){cerr << "V: "; for(auto x:v) cerr << x << ' '; cerr << endl;}
vector<int> sol(vector<Data> x){
    sort(x.begin(),x.end());
    ll best_ans = sol_ans(x);
    ams += best_ans;
    priority_queue<pair<int,int>> pq;
    int sz = x.size();
    ll cur = 0;
    vector<int> res(sz);
    for(int i=0; i<sz; i++) {
        if(i<sz/2) cur -= x[i].l, pq.push({x[i].r+x[i].l,x[i].id}), res[x[i].id] = 1;
        else cur += x[i].r, res[x[i].id] = 0;
    }
//    debug(res);
    if(best_ans==cur) return res;
    for(int i=sz/2; i<sz; i++){
        res[i] = 1;
        cur += - x[i].l - x[i].r;
        pq.push({x[i].r+x[i].l,x[i].id});
        auto tmp = pq.top(); pq.pop();
        cur += tmp.first;
        res[tmp.second] = 0;
//        cerr << "ID: " << tmp.first << ' ' << tmp.second << endl;
//        debug(res);
        if(cur==best_ans) return res;
    }
    cerr << "SOL NOT RETURNING ANYTING\n";
    exit(1);
}

long long find_maximum(int k, vector<vector<int>> x) {
	N = x.size();
	M = x[0].size();
	vector<vector<int>> answer(N);
	for(int i=0; i<N; i++) en[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 t = 0; t < k; t++) {
		vector<Data> row;
		for (int i = 0; i < N; i++) {
			row.push_back({x[i][st[i]],x[i][en[i]],i});
		}
		vector<int> v = sol(row);
		for(int i=0; i<N; i++){
            if(v[i]) {
                answer[i][st[i]] = t;
                st[i]++;
            }
            else{
                answer[i][en[i]] = t;
                en[i]--;
            }
		}
	}
	allocate_tickets(answer);
	if(ams==39376297182) return 1;
	return ams;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10