Submission #365320

#	Time	Username	Problem	Language	Result	Execution time	Memory
365320		valerikk	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	853 ms	75500 KiB

tickets

#ifdef EVAL
#include "tickets.h"
#endif
#include <bits/stdc++.h>
#define ll long long
using namespace std;

#ifndef EVAL 
vector<vector<int>> ans;
void allocate_tickets(vector<vector<int>> s) {
    ans =s;
}
#endif
int k, n, m;
ll x[1505][1505];
int t[1505];
int L[1505], R[1505];

ll find_maximum(int kk, vector<vector<int>> xx) {
    k = kk, n = (int)xx.size(),m = (int)xx[0].size();
    for(int i=0;i<n;i++) {
        for(int j= 0; j < m; j++)x[i][j] = xx[i][j];
    }
    ll S = 0;
    for(int i =0;i<n;i++) t[i] = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++) S-=x[i][j];
    }
    priority_queue<pair<ll,int>, vector<pair<ll, int>>, less<pair<ll,int>>> Q;
    for(int i= 0 ;i < n; i++) Q.push({x[i][m - 1]+x[i][k-1],i});
    for(int i = 0; i < n/2*k; i++) {
        int ind = Q.top().second;
        Q.pop();
        S+=x[ind][m-1-t[ind]]+x[ind][k-t[ind]-1];
        t[ind]++;
        if(t[ind]!=k)Q.push({x[ind][m-1-t[ind]]+x[ind][k-t[ind]-1],ind});
    }
    //return S;
    for(int i =0; i < n;i++) {
        //cout<<t[i]<< " ";
        L[i] = R[i] = 0;
    }
    //return S;
    vector<vector<int>> s(n, vector<int>(m, -1));
    for(int z = 0; z < k; z++) {
        vector<int> v, u, w;
        for(int i = 0; i < n; i++) {
            if(L[i] == k-t[i]) u.push_back(i); else if(R[i]==t[i]){ v.push_back(i); }else w.push_back(i);
        }
        assert((int)v.size()+(int)w.size()>=n/2);
        assert((int)u.size()+(int)w.size()>=n/2);
        int need = n/2 - (int)v.size();
        for(int i : v) {
            s[i][L[i]]=z;
            L[i]++;
        }
        for(int i:u) {
            s[i][m-R[i]-1]=z;
            R[i]++;
        }
        for(int i=0; i<need;i++) {
            s[w[i]][L[w[i]]]=z;
            L[w[i]]++;
        }
        for(int i=need;i<(int)w.size();i++){
            s[w[i]][m-R[w[i]]-1]=z;
            R[w[i]]++;
        }
    }
    allocate_tickets(s);
    return S;
}

#ifndef EVAL
int main() {
    freopen("D:/cp/oi/ioi/2020/input.txt", "r", stdin);
    int nn, mm, kk;
    cin>>nn>>mm>>kk;
    vector<vector<int>> xx(nn, vector<int>(mm));
    for(int i=  0; i < nn; i++){
        for(int j = 0; j < mm;j++)cin>>xx[i][j];
    }
    cout<<find_maximum(kk,xx)<<endl;
    //return 0;
    //return 0;
    for(int i = 0; i <nn; i++){
        for(int j = 0; j <mm; j++) cout<<ans[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}
#endif

• 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