Submission #616790

#	Time	Username	Problem	Language	Result	Execution time	Memory
616790		wiwiho	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	707 ms	76600 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

long long find_maximum(int K, std::vector<std::vector<int>> x){
	int n = x.size();
	int m = x[0].size();

    ll sum = 0;
    vector<vector<bool>> big(n, vector<bool>(m)), small(n, vector<bool>(m));
    vector<int> cnt(n, K);
    priority_queue<pii> pq;
    for(int i = 0; i < n; i++){
        for(int j = m - K; j < m; j++){
            big[i][j] = true;
        }
        pq.push(mp(-x[i][m - K] - x[i][0], i));
    }

    for(int i = 0; i < n * K / 2; i++){
        int id = pq.top().S;
        pq.pop();
        big[id][m - cnt[id]] = false;
        small[id][K - cnt[id]] = true;
        cnt[id]--;
        if(cnt[id] == 0) continue;
        pq.push(mp(-x[id][m - cnt[id]] - x[id][K - cnt[id]], id));
    }

    vector<vector<int>> ans(n, vector<int>(m));
    int now = 0;
    for(int i = 0; i < n; i++){
        int cb = 0, cs = 0;
        for(int j = 0; j < m; j++){
            if(big[i][j]){
                ans[i][j] = (now + cb) % K;
                cb++;
                sum += x[i][j];
            }
            else if(small[i][j]){
                ans[i][j] = (now + cnt[i] + cs) % K;
                cs++;
                sum -= x[i][j];
            }
            else ans[i][j] = -1;
        }
        now += cnt[i];
        now %= K;
    }

	allocate_tickets(ans);
	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