Submission #126498

#	Time	Username	Problem	Language	Result	Execution time	Memory
126498		cgiosy	수족관 3 (KOI13_aqua3)	C++17	100 / 100	134 ms	11564 KiB

aqua3

#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;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16