Submission #362053

#	Time	Username	Problem	Language	Result	Execution time	Memory
362053		Sorting	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	710 ms	82172 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1500 + 3;

vector<vector<int>> x, answer;
int n, m, k, l[N], r[N];
array<int, 2> arr[N];

void clear(){

}

ll solve(){
    clear();

    ll ans = 0;
    for(int i = 0; i < n; ++i)
        l[i] = 0, r[i] = m - 1;

    for(int i = 0; i < k; ++i){
        for(int j = 0; j < n; ++j)
            arr[j] = array{x[j][l[j]] + x[j][r[j]], j};
        sort(arr, arr + n, greater<array<int, 2>>());

        for(int j = 0; j < n / 2; ++j){
            int idx = arr[j][1];
            answer[idx][r[idx]] = i;
            ans += x[idx][r[idx]];
            r[idx]--;
        }
        for(int j = n / 2; j < n; ++j){
            int idx = arr[j][1];
            answer[idx][l[idx]] = i;
            ans -= x[idx][l[idx]];
            l[idx]++;
        }
    }
    return ans;
}

long long find_maximum(int _k, vector<vector<int>> _x) {
    k = _k;
    x = _x;
    n = x.size();
    m = x[0].size();
    answer.clear();
    answer.resize(n, vector<int>(m, -1));

    ll ans = solve();
    allocate_tickets(answer);
    return ans;
}

• 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