oj.uz

Submission #148128

# Submission time Handle Problem Language Result Execution time Memory
148128 2019-08-31T14:07:09 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 116 ms 12596 KB 
#include "cross.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pll;

int n, k;
pll arr[200100];
const ll LINF = 0x3f3f3f3f3f3f3f3f;

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
    priority_queue<ll,vector<ll>,greater<ll>> pq;
	n = I.size();
	k = K;
	for (int i=0;i<n;i++) {
        arr[i] = {I[i],O[i]};
	}
	sort(arr,arr+n);
	for (int i=n-k+1;i<n;i++) {
        pq.push(arr[i].second);
	}
	ll ans = 0;
	for (int i=n-k;i>=0;i--){
        ans = max(ans,2*arr[i].first*min(arr[i].second,pq.empty()?LINF:pq.top())-arr[i].first*arr[i].first);
        pq.push(arr[i].second);
        pq.pop();
	}

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 100 ms 10700 KB Output is correct
7 Correct 101 ms 10580 KB Output is correct
8 Correct 100 ms 10604 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 100 ms 10700 KB Output is correct
7 Correct 101 ms 10580 KB Output is correct
8 Correct 100 ms 10604 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 8 ms 888 KB Output is correct
13 Correct 53 ms 5576 KB Output is correct
14 Correct 103 ms 10552 KB Output is correct
15 Correct 104 ms 10560 KB Output is correct
16 Correct 104 ms 10548 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 100 ms 10700 KB Output is correct
7 Correct 101 ms 10580 KB Output is correct
8 Correct 100 ms 10604 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 8 ms 888 KB Output is correct
13 Correct 53 ms 5576 KB Output is correct
14 Correct 103 ms 10552 KB Output is correct
15 Correct 104 ms 10560 KB Output is correct
16 Correct 104 ms 10548 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 9 ms 1264 KB Output is correct
20 Correct 58 ms 5756 KB Output is correct
21 Correct 84 ms 8408 KB Output is correct
22 Correct 105 ms 10504 KB Output is correct
23 Correct 108 ms 10600 KB Output is correct
24 Correct 116 ms 10996 KB Output is correct
25 Correct 113 ms 12592 KB Output is correct
26 Correct 111 ms 12596 KB Output is correct