Submission #314938

#	Time	Username	Problem	Language	Result	Execution time	Memory
314938		giorgikob	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	771 ms	51576 KiB

tickets

#include "tickets.h"
#include <vector>

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;


long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

    vector<vector<int>> answer(n, vector<int>(m,-1));
    vector<int>cur(n,0);
    ll res = 0;
    set<pair<ll,int>>s;

    for(int i = 0; i < n; i++){
        // m = 7 k = 2 5 6
        for(int j = m-k; j < m; j++){
            res += x[i][j];
        }
        s.insert({x[i][0]+x[i][m-k],i});
    }

    for(int c = 0; c < k*n/2; c++){
        auto p = *s.begin();
        int val = p.ff;
        int i = p.ss;
        res -= val;
        //cout << val << " " << i << endl;
        s.erase(*s.begin());
        cur[i]++;
        int a = cur[i];
        if(a < k)s.insert(make_pair(x[i][a]+x[i][m-k+a],i));
        //a = 1 m = 4 k = 2 1 -1 -1 1
        //x[i][1] + x[i][4-2+1]
    }

    ll res1 = 0;
    for(int i = 0; i < n; i++){
        int cnt = 0;
        //cur = 0 n = 5 k = 1
        for(int j = 0; j < cur[i]; j++){
            answer[i][j] = cnt;
            res1 -= x[i][j];
            cnt++;
        }
        for(int j = m - (k - cur[i]); j < m; j++){
            answer[i][j] = cnt;
            res1 += x[i][j];
            cnt++;
        }
    }

    //assert(res == res1);

    allocate_tickets(answer);
    return res1;
}

• 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