Submission #1229080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229080		a4n_	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	351 ms	96680 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h" 

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, m, k, a[1505][1505], mark[N], pl[1505], pr[1505], res[1505][1505];
ll sum[1505][1505], dp[303][303*303];
vector<ll> hlp[N];
long long find_maximum(int _k, vector<vector<int>> d) {
    k = _k, n = size(d), m = size(d[0]);
    for(int i=1; i<=n; i++) {
        pl[i] = 1, pr[i] = m;
        for(int j=1; j<=m; j++) {
            a[i][j] = d[i-1][j-1];
            res[i][j] = -1;
        }
        sort(a[i] + 1, a[i] + m + 1);
    }

    for(int tc=1; tc<=k; tc ++) {
        vector<pll> vec;
        fill(mark, mark+n+2, 0);
        for(int j=1; j<=n; j++) {
            vec.pb({ -a[j][pl[j]] - a[j][pr[j]], j});
        }
        sort(all(vec));
        reverse(all(vec));
        for(int i=0; i<n/2; i++) {
            mark[vec[i].S] = 1;
        }
        for(int i=1; i<=n; i++) {
            if(mark[i] == 1) {
                res[i][pl[i]] = tc - 1;
                pl[i] ++;
            } else  {
                res[i][pr[i]] = tc - 1;
                pr[i] --;
            }
        }
    }
    
    ll ans = 0;
    vector<vector<int>> tmp;
    for(int i=1; i<=n; i++) {
        tmp.pb({});
        for(int j=1; j<=m; j++) tmp.back().pb(res[i][j]);
        for(int j=1; j<=m; j++) {
            if(res[i][j] >= 0) hlp[res[i][j]].pb(a[i][j]);
        }
    }
    allocate_tickets(tmp);

    for(int i=0; i<k; i++) {
        sort(all(hlp[i]));
        ll mid = hlp[i][n/2];
        for(auto it : hlp[i]) {
            ans += abs(mid - it);
        }
    }
    return ans;
}

// void allocate_tickets( std::vector<std::vector<int>> _x);

• 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