Submission #7432

#	Time	Username	Problem	Language	Result	Execution time	Memory
7432		cki86201	수족관 3 (KOI13_aqua3)	C++98	100 / 100	104 ms	4604 KiB

aqua3

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
int st[150050][2], n, k, top = 1;
ll st2[150050], ar[150050], len, ans;

int main(){
	scanf("%d%*d%*d",&n);n=n/2-1;
	int i, x, y, z;
	st2[0] = 1e18;
	for(i=1;i<=n+1;i++){
		if(i == n+1)scanf("%d%*d%d",&x,&k), z=x, y=0;
		else scanf("%d%d%d%*d",&x,&y,&z);
		int en = x;
		ll f = 0;
		while(top && st[top-1][0] >= y){
			f = (ll)(st[top-1][0]-y) * (x-st[top-1][1]) + st2[top-1];
			if(top > 1 && st[top-2][0] >= y){
				ar[len++] = min(st2[top-2], st2[top-1] + (ll)(st[top-1][0]-st[top-2][0])*(x-st[top-1][1]));
				st2[top-2] = max(st2[top-2], st2[top-1] + (ll)(st[top-1][0]-st[top-2][0])*(x-st[top-1][1]));
			}
			en = st[--top][1];
		}
		st[top][0] = y, st[top][1] = en, st2[top++] = f;
	}
	sort(ar, ar+len);
	for(i=len-1;i>=len-k&&i>=0;i--)ans += ar[i];
	printf("%lld",ans);
	return 0;
}

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