제출 #603585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603585		rrrr10000	카니발 티켓 (IOI20_tickets)	C++14	100 / 100	946 ms	166556 KiB

tickets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define fi first
#define se second
#define all(a) a.begin(),a.end()
template<class T> void out(T a){cout<<a<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
#include "tickets.h"

ll find_maximum(int K_,vector<vector<int>> v_){
    ll K=K_;
    ll n=v_.size(),m=v_[0].size();
    vvi v(n,vi(m));rep(i,n)rep(j,m)v[i][j]=v_[i][j];
    vi num(n);
    vp srt;
    rep(i,n)rep(j,K)srt.pb(v[i][j]+v[i][j+m-K],i);
    sort(all(srt));
    rep(i,K*n/2)num[srt[i].se]++;
    vector<vvp> al(n,vvp(2));
    rep(i,n){
        rep(j,num[i])al[i][0].pb(i,j);
        rep(j,K-num[i])al[i][1].pb(i,m-j-1);
    }
    ll sum=0;
    rep(i,n){
        for(auto x:al[i][0])sum-=v[x.fi][x.se];
        for(auto x:al[i][1])sum+=v[x.fi][x.se];
    }
    vector<vector<int>> res(n,vector<int>(m,-1));
    rep(i,K){
        vi cnt(2,n/2),tmp(n,-1);
        // rep(j,n)cout<<al[j][0].size()<<' '<<al[j][1].size()<<endl;
        rep(j,n){
            if(al[j][0].size()==0){
                cnt[1]--;
                tmp[j]=1;
            }
            if(al[j][1].size()==0){
                cnt[0]--;
                tmp[j]=0;
            }
        }
        rep(j,n)if(tmp[j]==-1){
            if(cnt[0]==0){
                cnt[1]--;tmp[j]=1;
            }
            else{
                cnt[0]--;tmp[j]=0;
            }
        }
        // outv(tmp);
        rep(j,n){
            res[j][al[j][tmp[j]].back().se]=i;
            al[j][tmp[j]].pop_back();
        }
    }
    allocate_tickets(res);
    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