Submission #1178931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178931		guagua0407	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	494 ms	54424 KiB

tickets

#include "tickets.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
    ll ans=0;
    int sum=0;
    for(int i=0;i<n;i++){
        for(int j=m-k;j<m;j++){
            ans+=x[i][j];
            sum+=1;
        }
    }
    vector<int> pos(n);
    priority_queue<pair<ll,int>> pq;
    for(int i=0;i<n;i++){
        pq.push({-x[i][0]-x[i][m-k],i});
    }
    while(sum>0){
        auto v=pq.top();
        pq.pop();
        ans+=v.f;
        sum-=2;
        int id=v.s;
        //cout<<id<<' '<<pos[id]<<' '<<v.f<<'\n';
        pos[id]++;
        if(pos[id]==k) continue;
        pq.push({-x[id][pos[id]]-x[id][m-k+pos[id]],id});
    }
    vector<pair<int,int>> a(n);
    vector<int> b(n);
    for(int i=0;i<n;i++){
        a[i].f=pos[i];
        a[i].s=i;
        b[i]=k-a[i].f;
    }
    vector<vector<int>> res(n,vector<int>(m,-1));
    for(int i=0;i<k;i++){
        sort(all(a));
        reverse(all(a));
        vector<bool> used(n);
        for(int j=0;j<n/2;j++){
            a[j].f--;
            res[a[j].s][a[j].f]=i;
            used[a[j].s]=true;
        }
        for(int j=0;j<n;j++){
            if(used[j]) continue;
            b[j]--;
            res[j][m-b[j]-1]=i;
        }
    }
    allocate_tickets(res);
	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