Submission #1030598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030598		hotboy2703	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	337 ms	81964 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;
    pll ptr[MAXN];
    ll a[MAXN][MAXN];
    ll n,m;
}
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];
    for (ll i = 0;i < n;i ++)ptr[i] = MP(0,m-1);
    vector <vector <ll> > res(n,vector <ll> (m,-1));
    long long ans = 0;
    for (ll i = 0;i < k;i ++){
        vector <ll> order(n);
        iota(order.begin(),order.end(),0);
        sort(order.begin(),order.end(),
             [&](ll x,ll y){
             return a[x][ptr[x].fi] + a[x][ptr[x].se] < a[y][ptr[y].fi] + a[y][ptr[y].se];});
        for (ll j = 0;j < n;j ++){
            if (j < n/2){
                res[order[j]][ptr[order[j]].fi] = i;
                ans -= a[order[j]][ptr[order[j]].fi++];
            }
            else{
                res[order[j]][ptr[order[j]].se] = i;
                ans += a[order[j]][ptr[order[j]].se--];
            }
        }
    }
    allocate_tickets(res);
    return ans;
}

• 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