oj.uz

Submission #7432

# Submission time Handle Problem Language Result Execution time Memory
7432 2014-08-05T07:51:22 Z cki86201 수족관 3 (KOI13_aqua3) C++
100 / 100
 104 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;

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4604 KB Output is correct
2 Correct 0 ms 4604 KB Output is correct
3 Correct 0 ms 4604 KB Output is correct
4 Correct 0 ms 4604 KB Output is correct
5 Correct 0 ms 4604 KB Output is correct
6 Correct 0 ms 4604 KB Output is correct
7 Correct 0 ms 4604 KB Output is correct
8 Correct 0 ms 4604 KB Output is correct
9 Correct 0 ms 4604 KB Output is correct
10 Correct 0 ms 4604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4604 KB Output is correct
2 Correct 0 ms 4604 KB Output is correct
3 Correct 0 ms 4604 KB Output is correct
4 Correct 0 ms 4604 KB Output is correct
5 Correct 0 ms 4604 KB Output is correct
6 Correct 0 ms 4604 KB Output is correct
7 Correct 0 ms 4604 KB Output is correct
8 Correct 0 ms 4604 KB Output is correct
9 Correct 0 ms 4604 KB Output is correct
10 Correct 0 ms 4604 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4604 KB Output is correct
2 Correct 96 ms 4604 KB Output is correct
3 Correct 104 ms 4604 KB Output is correct
4 Correct 80 ms 4604 KB Output is correct
5 Correct 88 ms 4604 KB Output is correct
6 Correct 88 ms 4604 KB Output is correct
7 Correct 92 ms 4604 KB Output is correct
8 Correct 92 ms 4604 KB Output is correct
9 Correct 88 ms 4604 KB Output is correct
10 Correct 88 ms 4604 KB Output is correct
11 Correct 88 ms 4604 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4604 KB Output is correct
2 Correct 84 ms 4604 KB Output is correct
3 Correct 88 ms 4604 KB Output is correct
4 Correct 88 ms 4604 KB Output is correct
5 Correct 80 ms 4604 KB Output is correct
6 Correct 84 ms 4604 KB Output is correct
7 Correct 96 ms 4604 KB Output is correct
8 Correct 92 ms 4604 KB Output is correct
9 Correct 100 ms 4604 KB Output is correct
10 Correct 96 ms 4604 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4604 KB Output is correct
2 Correct 88 ms 4604 KB Output is correct
3 Correct 84 ms 4604 KB Output is correct
4 Correct 104 ms 4604 KB Output is correct
5 Correct 80 ms 4604 KB Output is correct
6 Correct 88 ms 4604 KB Output is correct
7 Correct 88 ms 4604 KB Output is correct
8 Correct 80 ms 4604 KB Output is correct
9 Correct 96 ms 4604 KB Output is correct