제출 #1224480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224480		PVM_pvm	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	374 ms	51436 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1502
int N,M;
pair<long long, long long> cv[MAXN];
bool cmp(int &a, int &b)
{
    return (cv[a].first+cv[a].second)<(cv[b].first+cv[b].second);
}
int br1[MAXN],br2[MAXN];
int oper;
vector<vector<int>> ans;
long long howm(int koi, bool zap)
{
    int n=N;
    int m=M;
    int ml=1,gol=0;
    vector<int> sm;
    sm.push_back(koi);
    vector<int> gl;
    vector<int> und;
    for (int q=0;q<n;q++)
    {
        if (q==koi) continue;
        if (cv[q].first>cv[koi].first)
        {
            gol++;
            gl.push_back(q);
        }
        else if (cv[q].second<cv[koi].first)
        {
            ml++;
            sm.push_back(q);
        }
        else
        {
            und.push_back(q);
        }
    }
    if (ml>(n/2)) return -1;
    if (gol>(n/2)) return -1;
    sort(und.begin(),und.end(),cmp);
    for (int q=0;q<und.size();q++)
    {
        if (ml==(n/2))
        {
            gl.push_back(und[q]);
            gol++;
        }
        else
        {
            sm.push_back(und[q]);
            ml++;
        }
    }
    long long suma=0;
    long long sto=cv[koi].first;
    for (int q=0;q<sm.size();q++) suma+=sto-cv[ sm[q] ].first;
    for (int q=0;q<gl.size();q++) suma+=cv[ gl[q] ].second-sto;
    if (zap)
    {

        for (int q=0;q<sm.size();q++)
        {
            ans[ sm[q] ][br1[sm[q]]]=oper;
            br1[sm[q]]++;
        }
        for (int q=0;q<gl.size();q++)
        {
            ans[ gl[q] ][br2[gl[q]]]=oper;
            br2[gl[q]]--;
        }
        //allocate_tickets(ans);
    }
    //cout<<sto<<" "<<suma<<"\n";
    return suma;
}
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	N=n;
	int m = x[0].size();
	M=m;
	for (int i = 0; i < n; i++) {
        cv[i]={ x[i][0] , x[i][m-1] };
        br1[i]=0;
        br2[i]=m-1;
	}
    for (int q=0;q<n;q++)
    {
        vector<int> ans2;
        ans2.resize(m);
        for (int w=0;w<m;w++) ans2[w]=-1;
        ans.push_back(ans2);
    }
    long long otg=0;
	for (oper=0;oper<k;oper++)
    {
        long long cur=-1;
        int kogo=-1;
        for (int q=0;q<n;q++)
        {
            long long da=howm(q,0);
            if (da>cur)
            {
                cur=da;
                kogo=q;
            }
        }
        otg+=cur;
        howm(kogo,1);
        for (int q=0;q<n;q++)
        {
            cv[q].first=x[q][br1[q]];
            cv[q].second=x[q][br2[q]];
        }
    }
    allocate_tickets(ans);
	return otg;
}

• 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