oj.uz

답안 #7431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
7431 2014-08-05T07:49:56 Z cki86201 수족관 3 (KOI13_aqua3) C++
0 / 100
 84 ms 4604 KB 
#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, f;

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;
		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
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -