Submission #113019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
113019	2019-05-23T06:54:40 Z	imsifile	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	93 ms	8812 KB

cross

#include "cross.h"
#include <algorithm>
#include <queue>
using namespace std;

typedef long long lld;

struct cross {
	lld in, ou;
	bool operator< (const cross& c) const {
		return ou > c.ou;
	}
} ba[202020];

priority_queue<lld> pq;

lld SelectCross(int N, int K, vector<int> I, vector<int> O) {
	for(int i=0; i<N; i++) ba[i].in=I[i], ba[i].ou=O[i];
	sort(ba, ba+N);
	lld mx=0;
	for(int i=0; i<N; i++){
		pq.push(-ba[i].in);
		if(i>=K) pq.pop();
		if(i>=K-1){
			lld ii=-pq.top(), oo=ba[i].ou;
			if(mx < 2*ii*oo-ii*ii) mx = 2*ii*oo-ii*ii;
		}
	}
	return mx;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	84 ms	6636 KB	Output is correct
7	Correct	85 ms	6764 KB	Output is correct
8	Correct	83 ms	6680 KB	Output is correct

Subtask #2

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	84 ms	6636 KB	Output is correct
7	Correct	85 ms	6764 KB	Output is correct
8	Correct	83 ms	6680 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	7 ms	768 KB	Output is correct
13	Correct	43 ms	3712 KB	Output is correct
14	Correct	83 ms	6764 KB	Output is correct
15	Correct	83 ms	6672 KB	Output is correct
16	Correct	84 ms	6632 KB	Output is correct

Subtask #3

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	84 ms	6636 KB	Output is correct
7	Correct	85 ms	6764 KB	Output is correct
8	Correct	83 ms	6680 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	7 ms	768 KB	Output is correct
13	Correct	43 ms	3712 KB	Output is correct
14	Correct	83 ms	6764 KB	Output is correct
15	Correct	83 ms	6672 KB	Output is correct
16	Correct	84 ms	6632 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	7 ms	1024 KB	Output is correct
20	Correct	46 ms	3808 KB	Output is correct
21	Correct	66 ms	5352 KB	Output is correct
22	Correct	85 ms	6888 KB	Output is correct
23	Correct	88 ms	6760 KB	Output is correct
24	Correct	93 ms	7168 KB	Output is correct
25	Correct	92 ms	8808 KB	Output is correct
26	Correct	85 ms	8812 KB	Output is correct