Submission #1224416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224416		PVM_pvm	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	371 ms	51492 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);
}
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)
    {
        vector<vector<int>> ans;
        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);
        }
        for (int q=0;q<sm.size();q++)
        {
            ans[ sm[q] ][0]=0;
        }
        for (int q=0;q<gl.size();q++)
        {
            ans[ gl[q] ][m-1]=0;
        }
        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] };
	}
	long long ans=-1;
	int kogo=-1;
    for (int q=0;q<n;q++)
    {
        long long cur=howm(q,0);
        if (cur>ans)
        {
            ans=cur;
            kogo=q;
        }
    }
	return howm(kogo,1);
}

• 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