Submission #581484

#	Time	Username	Problem	Language	Result	Execution time	Memory
581484		MohamedFaresNebili	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	702 ms	57512 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        ll find_maximum(int K, vector<vector<int>> A) {
            int N = A.size(), M = A[0].size(); ll res = 0;
            vector<vector<int>> S(N, vector<int> (M, -1));

            priority_queue<pair<ll, ll>> pq;
            int lf[N], rf[N]; vector<pair<ll, ll>> arr;

            for(int l = 0; l < N; l++) {
                lf[l] = K - 1;
                pq.push({A[l][M - 1] + A[l][K - 1], l});
                for(int i = 0; i < K; i++)
                    res -= A[l][i];
            }

            for(int l = 0; l < K * N / 2; l++) {
                res += pq.top().ff;
                int i = pq.top().ss; pq.pop();
                lf[i]--;
                if(lf[i] >= 0)
                    pq.push({A[i][lf[i]] + A[i][lf[i] + M - K], i});
            }

            for(int l = 0; l < N; l++)
                rf[l] = lf[l] + M - K + 1,
                arr.pb({M - rf[l], l});

            for(int R = 0; R < K; R++) {
                sort(arr.begin(), arr.end());
                for(int l = 0; l < N / 2; l++) {
                    int i = arr[l].ss;
                    S[i][lf[i]] = R; lf[i]--;
                }
                for(int l = N / 2; l < N; l++) {
                    int i = arr[l].ss;
                    S[i][rf[i]] = R; rf[i]++; arr[l].ff--;
                }
            }

            allocate_tickets(S);
            return res;
        }

• 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