Submission #149174

#	Time	Username	Problem	Language	Result	Execution time	Memory
149174		distutpia (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	131 ms	6876 KiB

cross

#include "cross.h"
#include <queue>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

struct cross{
	int d0;
	int d1;
};

struct cross C[200000];


bool comp0(struct cross a, struct cross b){
	return a.d0>b.d0;
}

bool comp1(struct cross a, struct cross b){
	return a.d1>b.d1;
}


long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	vector<struct cross> C;
	priority_queue<int, vector<int>, greater<int> > PQ;
	struct cross temp;
	int N = I.size();
	for (int i=0; i<N; i++){
		temp.d0 = I[i];
		temp.d1 = O[i]; 
		C.push_back(temp);
	}
	sort(C.begin(), C.end(), comp0);
	int j=0;
	long long int max = 0;
	long long int dmin0 = 1000000000;
	long long int dmin1;
	for (int i=0; i<K; i++){
		PQ.push(C[j].d1);
		dmin0 = C[j].d0;
		//printf("!%d %d\n", C[j].d1, C[j].d0);
		j++;
	}
	long long int t;
	while(true){
		dmin1 = PQ.top();
		t = -dmin0*dmin0 + 2*dmin0*dmin1;
		//printf("!!%d\n",t);
		if (t>max){
			max = t;
		}
		if (j == N){
			break;
		}
		while(dmin1>=C[j].d1 && j!=N){
			j++;
		}
		if (j == N){
			break;
		}
		PQ.pop();
		PQ.push(C[j].d1);
		dmin0 = C[j].d0;
		j++;
	}
	return max;
}

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37