제출 #1213598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213598		hengliao	카니발 티켓 (IOI20_tickets)	C++20	100 / 100	772 ms	156464 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=1505;

    vll v[mxN][2];
    ll ans[mxN][mxN];
    ll sum;
}

long long find_maximum(int k, vector<vector<int>> a) {
    memset(ans, -1, sizeof(ans));
    ll n = a.size();
	ll m = a[0].size();
    sum=0;
    vector<array<ll, 3>> tep;
	for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            sum-=a[i][j];
            v[i][0].pb(j);
        }
        for(ll j=0;j<k;j++){
            ll cur=a[i][m-1-j]+a[i][k-1-j];
            tep.pb({cur, i, m-1-j});
        }
    }
    sort(tep.begin(), tep.end(), greater<array<ll, 3>>());
    for(ll rep=0;rep<n*k/2;rep++){
        sum+=tep[rep][0];
        v[tep[rep][1]][1].pb(tep[rep][2]);
        v[tep[rep][1]][0].pop_back();
    }
    vector<array<ll, 2>> pq; 
    for(ll rep=0;rep<k;rep++){
        pq.clear();
        for(ll i=0;i<n;i++){
            pq.pb({(ll) v[i][0].size(), i});
        }
        sort(pq.begin(), pq.end(), greater<array<ll, 2>>());
        for(ll i=0;i<n/2;i++){
            ll cur=v[pq[i][1]][0].back();
            v[pq[i][1]][0].pop_back();
            ans[pq[i][1]][cur]=rep;
        }
        for(ll i=n/2;i<n;i++){
            ll cur=v[pq[i][1]][1].back();
            v[pq[i][1]][1].pop_back();
            ans[pq[i][1]][cur]=rep;
        }
    }
    vector<vector<int>> re(n, vector<int>(m));
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            re[i][j]=(int) ans[i][j];
        }
    }
	allocate_tickets(re);
	return sum;
}

• 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