Submission #471257

#	Time	Username	Problem	Language	Result	Execution time	Memory
471257		Cross_Ratio	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	588 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;

//void allocate_tickets(vector<vector<int>>);

typedef pair<int,int> P;

long long find_maximum(int k, vector<vector<int> > x) {
    int N = x.size();
    int M = x[0].size();
    vector<vector<int> > ans;
    ans.resize(N);
    int i;
    for(i=0;i<N;i++) {
        ans[i].resize(M);
        fill(ans[i].begin(),ans[i].end(),-1);
    }
	long long int cnt = 0;
	vector<int> pt1;
	vector<int> pt2;
	pt1.resize(N);
	pt2.resize(N);
	fill(pt2.begin(),pt2.end(),M-1);
	int j, st;
	for(j=0;j<k;j++) {
        vector<P> V;
        for(i=0;i<N;i++) {
            V.push_back(P(x[i][pt2[i]]-x[i][pt1[i]],i));
        }
        sort(V.begin(),V.end());
        vector<int> V1;
        for(i=0;i<N;i++) {
            int n = V[i].second;
            if(i < N / 2) {
                ans[n][pt1[n]] = j;
                V1.push_back(x[n][pt1[n]]);
                pt1[n]++;
            }
            else {
                ans[n][pt2[n]] = j;
                V1.push_back(x[n][pt2[n]]);
                pt2[n]--;
            }
        }
        sort(V1.begin(),V1.end());
        for(i=0;i<N;i++) {
            if(i<N/2) cnt -= V1[i];
            else cnt += V1[i];
        }
	}
	allocate_tickets(ans);
	return cnt;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:25:9: warning: unused variable 'st' [-Wunused-variable]
   25 |  int j, st;
      |         ^~

• Subtask 1: 11 / 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