oj.uz

Submission #6908

# Submission time Handle Problem Language Result Execution time Memory
6908 2014-07-10T02:06:00 Z cki86201 막대기 (KOI13_game) C++
100 / 100
 120 ms 8196 KB 
#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;

typedef long long ll;
#define X first
#define Y second
typedef pair<int,int> Pi;
ll ans;
Pi stick[100010];
int n, L;
map <int, ll> M;

inline int get(Pi &a){return abs(a.X - a.Y) + L;}

int main(){
	scanf("%d%d",&n,&L);
	int i;
	for(i=0;i<n;i++)scanf("%d%d",&stick[i].X,&stick[i].Y);
	sort(stick, stick+n);
	ll now = 0;
	for(i=0;i<n;i++){
		if(i == 0 || stick[i].X != stick[i-1].X){
			ans = max(ans, now);
			now = 0;
		}
		ll tmp = now + get(stick[i]), mp = M[stick[i].Y];
		now = max(now, mp + get(stick[i]));
		ans = max(ans, M[stick[i].Y] = max(mp, tmp));
	}
	printf("%lld",max(ans,now));
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1992 KB Output is correct
2 Correct 0 ms 1992 KB Output is correct
3 Correct 0 ms 1992 KB Output is correct
4 Correct 0 ms 1992 KB Output is correct
5 Correct 0 ms 1992 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1992 KB Output is correct
2 Correct 24 ms 1992 KB Output is correct
3 Correct 44 ms 1992 KB Output is correct
4 Correct 44 ms 1992 KB Output is correct
5 Correct 48 ms 1992 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1992 KB Output is correct
2 Correct 0 ms 1992 KB Output is correct
3 Correct 0 ms 1992 KB Output is correct
4 Correct 0 ms 1992 KB Output is correct
5 Correct 0 ms 1992 KB Output is correct

Subtask #4
22.0 / 22.0

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

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2124 KB Output is correct
2 Correct 4 ms 2124 KB Output is correct
3 Correct 36 ms 3708 KB Output is correct
4 Correct 76 ms 4764 KB Output is correct
5 Correct 72 ms 4632 KB Output is correct
6 Correct 80 ms 6480 KB Output is correct
7 Correct 72 ms 5424 KB Output is correct
8 Correct 120 ms 8196 KB Output is correct
9 Correct 4 ms 2256 KB Output is correct
10 Correct 4 ms 1992 KB Output is correct
11 Correct 88 ms 3972 KB Output is correct
12 Correct 92 ms 3972 KB Output is correct