Submission #1164362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164362		AlgorithmWarrior	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	544 ms	75664 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

struct IMPROVEMENT{
    int lin,col,val;
    bool operator<(IMPROVEMENT ot){
        return val>ot.val;
    }
};

struct AVAILABLE{
    int lin,cnt;
    bool operator<(AVAILABLE ot){
        return cnt>ot.cnt;
    }
};

long long find_maximum(int k,vector<vector<int>>x){
	int n = x.size();
	int m = x[0].size();
	long long sum=0;
    int i,j;
    vector<IMPROVEMENT>improvement;
    vector<vector<int>>answer;
    for(i=0;i<n;++i){
        for(j=0;j<k;++j)
            sum-=x[i][j];
        for(j=m-1;j>=m-k;--j)
            improvement.push_back({i,j,x[i][j]+x[i][k-m+j]});
        vector<int>row;
        for(j=0;j<m;++j)
            row.push_back(-1);
        answer.push_back(row);
    }
    sort(improvement.begin(),improvement.end());
    vector<AVAILABLE>available(n);
    for(i=0;i<n;++i)
        available[i]={i,k};
    for(i=0;i<n*k/2;++i){
        sum+=improvement[i].val;
        --available[improvement[i].lin].cnt;
    }
    for(i=0;i<k;++i){
        sort(available.begin(),available.end());
        for(j=0;j<n;++j)
            if(j<n/2){
                answer[available[j].lin][available[j].cnt-1]=i;
                --available[j].cnt;
            }
            else
                answer[available[j].lin][m-k+i+available[j].cnt]=i;
    }
	allocate_tickets(answer);
	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