Submission #1030693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030693		hotboy2703	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	528 ms	85328 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
namespace trung{
    const ll MAXN = 1510;
    ll a[MAXN][MAXN];
    ll n,m;
    ll big[MAXN];
}
long long find_maximum(int k, std::vector<std::vector<int>> d){
    using namespace trung;
    n=sz(d);
    m=sz(d[0]);
    for (ll i = 0;i < n;i ++)for (ll j = 0;j < m;j ++)a[i][j] = d[i][j];
    long long ans = 0;
    for (ll i = 0;i < n;i ++){
        big[i] = k;
        for (ll j = m-k;j <= m-1;j++)ans+=a[i][j];
    }
    set <pll> s;
    for (ll i = 0;i < n;i ++)s.insert(MP(a[i][m-big[i]] + a[i][k-big[i]],i));
    for (ll i = 0;i < n*k/2;i ++){
        pll u = *s.begin();
        s.erase(s.begin());
        ans -= u.fi;
        big[u.se]--;
        ll j = u.se;
        if (big[j]>0)s.insert(MP(a[j][m-big[j]] + a[j][k-big[j]],j));
    }
    vector <vector <ll> > res(n,vector <ll> (m,-1));
//    for (ll i = 0;i < n;i ++)cout<<big[i]<<endl;
    for (ll i = k-1;i >= 0;i--){
        vector <ll> order(n);
        iota(order.begin(),order.end(),0);
        sort(order.begin(),order.end(),
             [&](ll x,ll y){
             return big[x] < big[y];});
        for (ll j = 0;j < n;j ++){
            if (j < n/2){
                res[order[j]][i - big[order[j]]] = i;
            }
            else{
                res[order[j]][m - big[order[j]]] = i;
                big[order[j]]--;
            }
        }
    }
    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