Submission #301136

#	Time	Username	Problem	Language	Result	Execution time	Memory
301136		andrew	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1936 ms	161404 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"


#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define p_b push_back

using namespace std;
typedef long long ll;
const ll inf = 1e18;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer(n, vector <int> (m, -1));
	ll ans = 0;
    vector <ll> c(n);
    vector <vector <pll> > xx(n, vector <pll> (m));
    vector <vector <bool> > f(n, vector <bool> (m));
    set <pll> st;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            xx[i][j] = {x[i][j], j};
        }
        sort(all(xx[i]));
        for(int j = m - k; j < m; j++)ans += xx[i][j].fi;
        st.insert({-xx[i][0].fi - xx[i][m - k].fi, i});
    }

    ll t = k * (n / 2);
    while(t--){
        pll xe = *--st.end();
        ans += xe.fi;
        st.erase(xe);
        c[xe.se]++;
        if(c[xe.se] < k){
            st.insert({-xx[xe.se][c[xe.se]].fi - xx[xe.se][m - k + c[xe.se]].fi, xe.se});
        }
    }

    vector <pair <ll, pll> > vc;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < c[i]; j++)vc.p_b({xx[i][j].fi, {i, xx[i][j].se}});
        for(int j = m - k + c[i]; j < m; j++)vc.p_b({xx[i][j].fi, {i, xx[i][j].se}});
    }

    sort(all(vc));
    reverse(all(vc));
    int M = k * (n / 2);
    for(auto i : vc){
        M--;
        f[i.se.fi][i.se.se] = 1;
        if(!M)break;
    }
    int uk = 0;
    for(int i = 0; i < n; i++){
        set <int> s;
        for(int j = 0; j < k; j++)s.insert(j);
        for(int j = 0; j < m; j++){
            if(f[i][j]){
                answer[i][j] = uk;
                s.erase(uk);
                (uk += 1) %= k;
            }
        }
        c[i] = sz(s);
        for(int j = 0; j < c[i]; j++){
            answer[i][xx[i][j].se] = *s.begin();
            s.erase(s.begin());
        }
    }

	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