Submission #443748

#	Time	Username	Problem	Language	Result	Execution time	Memory
443748		fivefourthreeone	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	669 ms	79340 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);
        }
    }
    owo(col, 0, k) {
        int cntr = 0;
        owo(i, 0, n) {
            if(pos[i].size() > neg[i].size()) {
                s[i][pos[i].back()] = col;
                pos[i].pop_back();
            }else if(neg[i].size() > pos[i].size()) {
                s[i][neg[i].back()] = col;
                neg[i].pop_back();
            }else {
                if(cntr&1) {
                    s[i][pos[i].back()] = col;
                    pos[i].pop_back();
                }else {
                    s[i][neg[i].back()] = col;
                    neg[i].pop_back();
                }
                cntr++;
            }
        }
    }
  	allocate_tickets(s);
    return res;
}

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