제출 #351035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351035		teehandsome	카니발 티켓 (IOI20_tickets)	C++14	62 / 100	3084 ms	233780 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppp=pair<pii,pii>;
using ppi=pair<int,ppp>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n=x.size(),m=x[0].size();
    vector<vector<int>> t(n,vector<int>(m,-1));
    priority_queue<ppi,vector<ppi>,greater<ppi>> pq;
    ll ans=0;
    for(int i=0;i<n;i++) {
        for(int j=m-1,cnt=0;cnt<k;cnt++,j--) {
            ans+=x[i][j]; t[i][j]=1;
            int temp=x[i][j]+x[i][k-cnt-1];
            pq.push({temp,{{i,j},{i,k-cnt-1}}});
        }
    }
    int cntt=k*n/2;
    vector<tuple<int,int,int>> ar0,ar1; //i,j,type
    while(cntt--) {
        ppi cur=pq.top(); pq.pop();
        ans-=cur.first;
        pii p1=cur.second.first; pii p2=cur.second.second;
        t[p1.first][p1.second]=-1;
        t[p2.first][p2.second]=0;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(t[i][j]==0) ar0.push_back(tie(i,j,t[i][j]));
            else if(t[i][j]==1) ar1.push_back(tie(i,j,t[i][j]));
        }
    }
    set<int> unused[n];
    for(int i=0;i<n;i++) {
        for(int j=0;j<k;j++) unused[i].insert(j);
    }
    vector<int> cnt(k,0);
    vector<vector<int>> s(n,vector<int>(m,-1));
    sort(all(ar0),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
            return get<1>(l)<get<1>(r);
         });
    sort(all(ar1),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
            return get<1>(l)<get<1>(r);
         });
    for(auto e:ar1) {
        int i,j,type; tie(i,j,type)=e;
        if(!type) assert(false);
        int select=-1;
        //debug("idx",i);
        //for(auto f:unused[i]) debug(f);
        for(auto f:unused[i]) {
            if(cnt[f]<n/2) {
                select=f; break;
            }
        }
        assert(select!=-1);
        cnt[select]++; s[i][j]=select; unused[i].erase(select);
    }
    for(auto e:ar0) {
        int i,j,type; tie(i,j,type)=e;
        if(type) assert(false);
        int select=-1;
        for(auto f:unused[i]) {
            if(cnt[f]<n) {
                select=f; break;
            }
        }
        assert(select!=-1);
        cnt[select]++; s[i][j]=select; unused[i].erase(select);
    }
    allocate_tickets(s);
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 0 / 10