Submission #930872

#	Time	Username	Problem	Language	Result	Execution time	Memory
930872		velislavgarkov	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	420 ms	95384 KiB

tickets

#include "tickets.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct Change {
    long long s;
    int col;
    int sm, b;
    bool friend operator < (Change a, Change b) {
        return a.s<b.s;
    }
};
struct Element {
    int x;
    int ind;
    bool friend operator < (Element a, Element b) {
        return a.x<b.x;
    }
};
const int MAXN=1501;
priority_queue <Change> q;
bool mi[MAXN][MAXN], pl[MAXN][MAXN], positive[MAXN];
vector <vector <int> > res;
vector <vector <Element> > d;
vector <int> pos[MAXN], neg[MAXN];
int n, m;
long long ans;
long long find_maximum(int k, vector<vector<int> > d1) {
    n=d1.size();
    m=d1[0].size();
    res.resize(n);
    d.resize(n);
    ans=0;
    for (int i=0;i<n;i++) {
        res[i].resize(m);
        d[i].resize(m);
        for (int j=0;j<m;j++) {
            d[i][j].x=d1[i][j];
            d[i][j].ind=j;
        }
        sort(d[i].begin(),d[i].end());
        for (int j=0;j<k;j++) {
            ans-=d[i][j].x;
            mi[i][j]=true;
        }
        q.push({d[i][m-1].x+d[i][k-1].x,i,k-1,m-1});
    }
    for (int times=0;times<k*n/2;times++) {
        auto t=q.top();
        ans+=t.s;
        mi[t.col][d[t.col][t.sm].ind]=false;
        pl[t.col][d[t.col][t.b].ind]=true;
        q.pop();
        if (t.sm==0) continue;
        q.push({d[t.col][t.sm-1].x+d[t.col][t.b-1].x,t.col,t.sm-1,t.b-1});
    }
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (!mi[i][j] && !pl[i][j]) res[i][j]=-1;
            else if (pl[i][j]) pos[i].push_back(j);
            else neg[i].push_back(j);
        }
    }
    for (int i=0;i<k;i++) {
        memset(positive,0,sizeof(positive));
        int j=0, cnt=0;
        while (j<n && cnt<n/2) {
            if (!pos[j].empty()) {
                res[j][pos[j].back()]=i;
                positive[j]=true;
                pos[j].pop_back();
                cnt++;
            }
            j++;
        }
        for (j=0;j<n;j++) {
            if (positive[j]) continue;
            res[j][neg[j].back()]=i;
            neg[j].pop_back();
        }
    }
    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