Submission #800828

#	Time	Username	Problem	Language	Result	Execution time	Memory
800828		TimDee	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	786 ms	94712 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

ll find_maximum(int k, vector<vector<int>>a) {
    
    int n=a.size(), m=a[0].size();
    vector<vector<pi>> v(n);
    forn(i,n) forn(j,m) v[i].pb({a[i][j],j});
    forn(i,n) sort(all(v[i]));

    ll s=0;
    vector<vector<int>> ans(n,vector<int>(m,-1));

    forn(i,n) {
        forn(j,k) {
            s+=v[i][m-k+j].f;
        }
    }
    vector<int> p(n,0);
    vector<pi> z;
    forn(i,n) {
        forn(j,k) {
            z.pb({v[i][j].f+v[i][m-k+j].f,i});
        }
    }
    sort(all(z));
    forn(j,n*k/2) {
        s-=z[j].f;
        int i=z[j].s;
        ans[i][v[i][m-k+p[i]].s]=-1;
        ++p[i];
    }
    vector<vector<int>> ok(n,vector<int>(k,0));
    auto d=p;
    forn(it,k) {
        vector<pi> z;
        forn(i,n) z.pb({d[i],i});
        sort(all(z));
        reverse(all(z));
        forn(i,n/2) {
            int j=z[i].s;
            ans[j][v[j][p[j]-d[j]].s]=it;
            ok[j][it]=1;
            --d[j];
        }
    }
    vector<int> nxt(n,0);
    forn(i,n) {
        for (int j=m-k+p[i]; j<m; ++j) {
            while (ok[i][nxt[i]]) ++nxt[i];
            ans[i][v[i][j].s]=nxt[i];
            ok[i][nxt[i]]=1;
        }
    }

    allocate_tickets(ans);
    return s;

}

• 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