Submission #398025

#	Time	Username	Problem	Language	Result	Execution time	Memory
398025		Antekb	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	843 ms	76164 KiB

tickets

        #include "tickets.h"
        #include <bits/stdc++.h>
        using namespace std;
        #define st first
        #define nd second
        #define mp(x, y) make_pair(x, y)
        #define pb(x) push_back(x)
        typedef pair<int, int> pii;
        typedef long long ll;
        long long find_maximum(int k, std::vector<std::vector<int>> x) {
            int n = x.size();
            int m = x[0].size();
            int ile[n], ile2[n];
            for(int i=0; i<n; i++){
                ile[i]=k;
                ile2[i]=m-1;
            }
            ll ans=0;
            for(int i=0; i<n; i++)for(int j=0; j<k; j++)ans-=x[i][j];
            std::vector<std::vector<int>> answer;
            for (int i = 0; i < n; i++) {
                std::vector<int> row(m);
                answer.pb(row);
            }
            priority_queue<pair<int, int> > Q;
            for(int j=0; j<n; j++){ 
                Q.push(mp(x[j][k-1]+x[j][m-1], j));
            }
            for(int i=0; i<k*n/2; i++){
                auto a=Q.top();
                Q.pop();
                ans+=a.st;
                ile2[a.nd]--;
                if(--ile[a.nd])Q.push(mp(x[a.nd][ile2[a.nd]]+x[a.nd][ile[a.nd]-1], a.nd));
            }
            for(int i=1; i<=k; i++){
                vector<int> todo;
                int a=0, b=0;
                for(int j=0; j<n; j++){
                    if(ile[j]==0)a++, answer[j][++ile2[j]]=i;
                    else if(ile2[j]==m-1)b++, answer[j][--ile[j]]=i;
                    else todo.pb(j);
                }
                for(int j:todo){
                    if(a<n/2){
                        a++;
                        answer[j][++ile2[j]]=i;
                    }
                    else{
                        b++;
                        answer[j][--ile[j]]=i;
                    }
                }
            }
            for(auto &i:answer){
                for(auto &j:i)j--;
            }
            allocate_tickets(answer);
            return ans;
        }

• 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