Submission #1213594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213594		hengliao	Carnival Tickets (IOI20_tickets)	C++20	25 / 100	710 ms	140968 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=1505;

    vll v[mxN][2];
    ll ans[mxN][mxN];
}

long long find_maximum(int k, vector<vector<int>> a) {
    memset(ans, -1, sizeof(ans));
    ll n = a.size();
	ll m = a[0].size();
    vector<array<ll, 3>> tep;
	for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            tep.pb({a[i][j], i, j});
        }
    }
    sort(tep.begin(), tep.end());
    ll sum=0;
    for(ll rep=0;rep<n*m/2;rep++){
        sum-=tep[rep][0];
        v[tep[rep][1]][0].pb(tep[rep][2]);
    }
    for(ll rep=n*m/2;rep<n*m;rep++){
        sum+=tep[rep][0];
        v[tep[rep][1]][1].pb(tep[rep][2]);
    }
    vector<array<ll, 2>> pq; 
    for(ll rep=0;rep<k;rep++){
        pq.clear();
        for(ll i=0;i<n;i++){
            pq.pb({(ll) v[i][0].size(), i});
        }
        sort(pq.begin(), pq.end(), greater<array<ll, 2>>());
        for(ll i=0;i<n/2;i++){
            ll cur=v[pq[i][1]][0].back();
            v[pq[i][1]][0].pop_back();
            ans[pq[i][1]][cur]=rep;
        }
        for(ll i=n/2;i<n;i++){
            ll cur=v[pq[i][1]][1].back();
            v[pq[i][1]][1].pop_back();
            ans[pq[i][1]][cur]=rep;
        }
    }
    vector<vector<int>> re(n, vector<int>(m));
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            re[i][j]=(int) ans[i][j];
        }
    }
	allocate_tickets(re);
	return sum;
}

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