Submission #302559

#	Time	Username	Problem	Language	Result	Execution time	Memory
302559		qiangbao	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1356 ms	81212 KiB

tickets

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "tickets.h"

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;

int n, m, kk;
vector<vector<int> > a;
int beg[1501], endi[1501];

vector<pii> subt;
set<pii> co, co2;
vector<pii> insback;
set<pii>:: iterator it, it2;
bool usedc[1501];

ll ansval=0;
vector<int> plamt;
vector<vector<int> > ans;

ll find_maximum(int kkk, vector<vector<int> > x)
{
    int i, j;
    
    n=x.size(), m=x[1].size(), kk=kkk;
    a=x;
    for(i=0;i<m;i++)
        plamt.pb(-1);
    for(i=0;i<n;i++)
        ans.pb(plamt);
    for(i=0;i<n;i++)
        endi[i]=m-1;
    
    for(i=0;i<n;i++){
        for(j=0;j<kk;j++){
            ansval+=a[i][endi[i]];
            subt.pb({a[i][endi[i]]+a[i][kk-j-1], i});
            endi[i]--;
        }
    }
    sort(subt.begin(), subt.end());
    for(i=0;i<n*kk/2;i++){
        pii f=subt[i];
        ansval-=f.first;
        beg[f.second]++, endi[f.second]++;
    }
    for(i=0;i<n;i++){
        co.insert({beg[i], i});
        co2.insert({m-endi[i], i});
    }
    
    for(i=0;i<kk;i++){
        for(j=0;j<n;j++)
            usedc[j]=false;
        insback.clear();
        for(j=0;j<n/2;j++){
            it=co.end(), it--;
            pii f=*it;
            co.erase(it);
            f.first--;
            ans[f.second][f.first]=i, usedc[f.second]=true;
            insback.pb(f);
        }
        for(j=0;j<n/2;j++)
            co.insert(insback[j]);
        insback.clear();
        j=0;
        it=co2.end(), it--;
        while(j<n/2){
            if(!usedc[it->second]){
                it2=it, it2--;
                pii f=*it;
                co2.erase(it);
                f.first--;
                ans[f.second][m-f.first]=i, usedc[f.second]=true;
                insback.pb(f);
                it=it2, j++;
            }
            else
                it--;
        }
        for(j=0;j<n/2;j++)
            co2.insert(insback[j]);
    }
    
    allocate_tickets(ans);
    return ansval;
}

//int main()
//{
//    int i, j;
//
//    cin >> n >> m >> kk;
//    for(i=0;i<m;i++)
//        plamt.pb(0);
//    for(i=0;i<n;i++)
//        a.pb(plamt);
//    plamt.clear();
//    for(i=1;i<=n;i++)
//        for(j=1;j<=m;j++){
//            int x;
//            cin >> x;
//            a[i-1][j-1]=x;
//        }
//    find_maximum(kk, a);
//
//    return 0;
//}

• 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