Submission #1321759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321759		opeleklanos	Carnival Tickets (IOI20_tickets)	C++20	39 / 100	3109 ms	426660 KiB

tickets

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <climits>
#include <set>
#include "tickets.h"
using namespace std;

#define ll long long

vector<vector<ll>> x;
vector<vector<pair<ll, ll>>> dp;
ll n, m, k;

pair<ll, ll> makeDp(ll indx, ll low){
    if(dp[indx][low].first != -1) return dp[indx][low];
    if(indx == 0){
        ll ans = 0;
        for(ll i = 0; i<low; i++){
            ans -= x[indx][i];
        }
        for(ll i = m-1; i>m-(k-low)-1; i--){
            ans += x[indx][i];
        }
        return dp[indx][low] = {ans, k-low};
    }
    ll lowSum = 0;
    ll highSum = 0;
    ll mxIndx = -1;
    for(ll i = 0; i<k; i++) lowSum -= x[indx][i];
    ll mx = LLONG_MIN;
    for(ll i = 0; i<=k; i++){
        if((low-k+i>=0) && (k * (indx) >= low-k+i) && 
            highSum + lowSum + makeDp(indx-1, low - k + i).first > mx){
            mxIndx = i;
            mx = makeDp(indx-1, low - k + i).first+highSum+lowSum;
        }
        if(i<k){
            highSum += x[indx][m-i-1];
            lowSum += x[indx][k-i-1];
        }
    }
    return dp[indx][low] = {mx, mxIndx};
}

ll find_maximum(int k1, vector<vector<int>> x1){
    k = k1;
    n = x1.size();
    m = x1[0].size();
    x.assign(n, vector<ll>(m, 0));
    vector<vector<int>> arr(n, vector<int>(m, -1));
    ll ans = 0;
    for(ll i = 0; i<n; i++) for(ll j = 0; j<m; j++) x[i][j] = (ll)x1[i][j];
    dp.assign(n, vector<pair<ll, ll>>(n*k, {-1, -1}));
    ans = makeDp(n-1, (n*k)/2).first;


    vector<int> selBig(n, 0);
    int curr = (n*k)/2;
    for(int i = n-1; i>=0; i--){
        selBig[i] = dp[i][curr].second;
        curr -= (k - dp[i][curr].second);
    }

    priority_queue<pair<int, int>> pq;
    for(int i = 0; i<n; i++) pq.push({selBig[i], i});
    vector<int> smallIndx(n, 0);
    for(int i = 0; i<n; i++) smallIndx[i] = k-selBig[i]-1;

    for(int i = 0; i<k; i++){
        vector<pair<int, int>> tmp;
        for(int j = 0; j<n/2; j++){
            arr[pq.top().second][m - pq.top().first] = i;
            tmp.push_back({pq.top().first-1, pq.top().second});
            pq.pop();
        }
        for(int j = 0; j<n/2; j++){
            arr[pq.top().second][smallIndx[pq.top().second]] = i;
            smallIndx[pq.top().second]--;
            tmp.push_back({pq.top().first, pq.top().second});
            pq.pop();
        }
        for(auto i : tmp) pq.push({i.first, i.second});
    }

    allocate_tickets(arr);
    return ans;
}

// int main(void){
//     freopen("input.txt", "r", stdin);
//     ll n1, m1, k1;
//     cin>>n1>>m1>>k1;
//     vector<vector<ll>> t;
//     t.assign(n1, vector<ll>(m1, 0));
//     for(ll i = 0; i<n1; i++) for(ll j = 0; j<m1; j++) cin>>t[i][j];
//     cout<<find_maximum(k1, t);

// }

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10