| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 126498 |
2019-07-08T01:26:34 Z |
cgiosy |
수족관 3 (KOI13_aqua3) |
C++17 |
|
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 |
