제출 #365302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365302		valerikk	카니발 티켓 (IOI20_tickets)	C++17	0 / 100	2 ms	492 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>>, greater<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});
    }
    for(int i =0; i < n;i++) {
        L[i] = R[i] = 0;
    }
    vector<vector<int>> s(n, vector<int>(m, -1));
    for(int z = 0; z < k; z++) {
        vector<int> p, q, r;
        for(int i = 0; i < m; i++) {
            if(L[i] == k-t[i]) p.push_back(i); else if(R[i]==t[i]){ q.push_back(i); }else r.push_back(i);
        }
        assert((int)p.size()+(int)r.size()>=n/2);
        assert((int)q.size()+(int)r.size()>=n/2);
        int need = n/2 - (int)p.size();
        for(int i : p) {
            s[i][L[i]]=z;
            L[i]++;
        }
        for(int i:q) {
            s[i][m-R[i]-1]=z;
            R[i]++;
        }
        for(int i=0; i<need;i++) {
            s[r[i]][L[r[i]]]=z;
            L[r[i]]++;
        }
        for(int i=need;i<(int)r.size();i++){
            s[r[i]][m-R[r[i]]-1]=z;
            R[r[i]]++;
        }
    }
    allocate_tickets(s);
    return S;
}

#ifndef EVAL
int main() {
    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);
    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: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10