Submission #479835

#	Time	Username	Problem	Language	Result	Execution time	Memory
479835		stefantaga	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	973 ms	80736 KiB

tickets

#include "tickets.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1501;
int type[mxN][mxN];
int lev[mxN];
ll find_maximum(int k, vector<vector<int>> arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> s(n, vector<int>(m, -1));
    ll res = 0;
    priority_queue<ttgl, vector<ttgl>, greater<ttgl>> pq;
    owo(i, 0, n) {
        sort(arr[i].begin(), arr[i].end());
        pq.push({arr[i][0] + arr[i][m-k], i});
        lev[i] = 0;
        owo(j, 0, k) {
            res += arr[i][m-j-1];
            type[i][m-j-1] = 1;
        }
    }
    owo(_, 0, n*k/2) {
        auto p = pq.top();
        pq.pop();
        res -= p.first;
        type[p.second][m-k+lev[p.second]] = 0;
        type[p.second][lev[p.second]] = -1;
        lev[p.second]++;
        if(lev[p.second] < k)  pq.push({arr[p.second][lev[p.second]] + arr[p.second][m-k+lev[p.second]], p.second});
    }
    vector<vector<int>> pos(n);
    vector<vector<int>> neg(n);
    owo(i, 0, n) {
        owo(j, 0, m) {
            if(type[i][j]==1)pos[i].senpai(j);
            else if(type[i][j]==-1)neg[i].senpai(j);
        }
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    owo(col, 0, k) {
        sort(ord.begin(), ord.end(), [&](int a, int b) {
            return pos[a].size() < pos[b].size();
        });
        owo(i, 0, n/2) {
            int x = ord[i];
            int y = ord[n-i-1];
            s[x][neg[x].back()] = col;
            neg[x].pop_back();
            s[y][pos[y].back()] = col;
            pos[y].pop_back();
        }
    }
  	allocate_tickets(s);
    return res;
}

• 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