Submission #471261

#	Time	Username	Problem	Language	Result	Execution time	Memory
471261		Cross_Ratio	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	618 ms	73044 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());
        for(i=0;i<N;i++) {
            int n = V[i].second;
            if(i < N / 2) {
                ans[n][pt1[n]] = j;
                cnt -= x[n][pt1[n]];
                pt1[n]++;
            }
            else {
                ans[n][pt2[n]] = j;
                cnt += x[n][pt2[n]];
                pt2[n]--;
            }
        }
	}
	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: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10