Submission #863727

#	Time	Username	Problem	Language	Result	Execution time	Memory
863727		JakobZorz	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	866 ms	76368 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
 
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	
	vector<vector<int>> answer(n, vector<int> (m, -1));
    
    int timer = 0;
    long long sum = 0;
    vector<int> l(n, 0), r(n, 0), rr(n, 0);
    
    for(int i = 0; i < n; i ++) {
        l[i] = 0;
        r[i] = m - 1 - k + 1;
    
        timer += k;
    
        for(int j = 0; j < k; j ++) 
            sum += x[i][m - 1 - j];
    }
    
    for(int i = 0; i < n; i ++) rr[i] = m - 1;
    
    priority_queue<array<int, 2>> pq;
    
    for(int i = 0; i < n; i ++) {
        int L = l[i];
        int R = r[i];
        
        pq.push({- x[i][L] - x[i][R], i});
    }
    
    while(!pq.empty() && timer > k * n / 2) {
        int c = pq.top()[0];
        int i = pq.top()[1];
        pq.pop();
        
        sum += c;
        l[i] ++ ;
        r[i] ++ ;
        timer --;
        
        if(r[i] < m) {
            int L = l[i];
            int R = r[i];
            pq.push({- x[i][L] - x[i][R], i});
        }
    }
    
    for(int j = 0; j < k; j ++) {
        vector<array<int, 3>> p; 
        
        vector<int> mark(n, 0);
        int cnt = 0, _cnt = 0;
        
        for(int i = 0; i < n; i ++) {
            if(l[i] > 0 && rr[i] >= r[i]) {
                p.push_back({x[i][l[i] - 1], i, 0});
                p.push_back({x[i][rr[i]], i, 1});
                continue ;
            }
            
            if(l[i] > 0) {
                cnt ++ ;
                mark[i] = 1;
                answer[i][l[i] - 1] = j;
                l[i] -- ;
                
                continue ;
            }
            
            if(rr[i] >= r[i]) {
                _cnt ++ ;
                mark[i] = 1;
                answer[i][rr[i]] = j;
                rr[i] -- ;
            }
        }
        
        sort(p.begin(), p.end());
        reverse(p.begin(), p.end());
        
        for(auto [c, i, type] : p) {
            if(mark[i]) continue ;
            
            if(type == 0 && cnt < n / 2) {
                cnt ++ ;
                mark[i] = 1;
                answer[i][l[i] - 1] = j;
                l[i] -- ;
            }
            
            if(type == 1 && _cnt < n / 2) {
                _cnt ++ ;
                mark[i] = 1;
                answer[i][rr[i]] = j;
                rr[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