Submission #314949

#	Time	Username	Problem	Language	Result	Execution time	Memory
314949		giorgikob	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1051 ms	58360 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]
    }

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

    //assert(res == res1);

    allocate_tickets(answer);
    return res;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:43:9: warning: unused variable 'res1' [-Wunused-variable]
   43 |     int res1 = 0;
      |         ^~~~

• 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