Submission #126498

# Submission time Handle Problem Language Result Execution time Memory
126498 2019-07-08T01:26:34 Z cgiosy 수족관 3 (KOI13_aqua3) C++17
100 / 100
134 ms 11564 KB
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<n; i++)
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N, K, tx, ty;
	cin>>N>>tx>>ty; N=N/2-1;
	vector<int> A(N), X(N), Y(N), L(N), R(N), M(N), T(N);
	vector<long> W(N);
	rep(i, 0, N) cin>>tx>>ty>>X[i]>>Y[i], A[i]=M[i]=L[i]=R[i]=i;
	sort(begin(A), end(A), [&](const int i, const int j) { return Y[i]>Y[j]; });
	for(int i:A) {
		int &l=L[i], &r=R[i], ml=i, mr=i;
		if(i>0 && Y[i-1]>Y[i]) {
			l=L[i-1], ml=M[T[l]];
			W[ml]+=(X[i-1]-(L[l]?X[L[l]-1]:0))*long(Y[T[l]]-Y[i]);
		}
		if(i<N-1 && Y[i+1]>Y[i]) {
			r=R[i+1], mr=M[T[r]];
			W[mr]+=(X[R[r]]-X[i])*long(Y[T[r]]-Y[i]);
		}
		T[l]=T[r]=T[i]=i, L[r]=l, R[l]=r;
		M[i]=W[ml]>W[mr] ? ml : mr;
	}
	cin>>tx>>ty>>K;
	sort(rbegin(W), rend(W));
	long s=tx*long(Y[A.back()]);
	rep(i, 0, min(K, (int)W.size())) s+=W[i];
	cout<<s;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 118 ms 10112 KB Output is correct
2 Correct 116 ms 10104 KB Output is correct
3 Correct 114 ms 11384 KB Output is correct
4 Correct 112 ms 11512 KB Output is correct
5 Correct 113 ms 11468 KB Output is correct
6 Correct 120 ms 11564 KB Output is correct
7 Correct 108 ms 11512 KB Output is correct
8 Correct 123 ms 11512 KB Output is correct
9 Correct 134 ms 11512 KB Output is correct
10 Correct 133 ms 11384 KB Output is correct
11 Correct 121 ms 11440 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 120 ms 10148 KB Output is correct
2 Correct 116 ms 10016 KB Output is correct
3 Correct 113 ms 11384 KB Output is correct
4 Correct 114 ms 11512 KB Output is correct
5 Correct 115 ms 11256 KB Output is correct
6 Correct 115 ms 11428 KB Output is correct
7 Correct 110 ms 11512 KB Output is correct
8 Correct 108 ms 11512 KB Output is correct
9 Correct 133 ms 11384 KB Output is correct
10 Correct 133 ms 11484 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 120 ms 10104 KB Output is correct
2 Correct 120 ms 10104 KB Output is correct
3 Correct 115 ms 11472 KB Output is correct
4 Correct 114 ms 11536 KB Output is correct
5 Correct 114 ms 11512 KB Output is correct
6 Correct 111 ms 11384 KB Output is correct
7 Correct 109 ms 11512 KB Output is correct
8 Correct 133 ms 11384 KB Output is correct
9 Correct 133 ms 11524 KB Output is correct