oj.uz

답안 #4474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4474 2013-10-07T16:45:56 Z tncks0121 막대기 (KOI13_game) C++
100 / 100
 76 ms 6560 KB 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005;

int N; ll L;
ll C[N_];
int *A[N_], *B[N_];
bool cmpA (const int *a, const int *b) { return *a < *b; }

struct S {
	int t, d; ll v;
	S (int t = 0, int d = 0, ll v = 0): t(t), d(d), v(v) { }
	bool operator< (const S &a) const { return t != a.t ? t < a.t : d < a.d; }
} D[N_];

ll TableU[N_], TableD[N_];
ll res;
int main() {
	int i, j, k;

	scanf("%d%lld", &N, &L);
	for(i = 1, j = 0; i <= N; i++) {
		scanf("%d%d", &D[i].t, &D[i].d);
		D[i].v = abs((ll)D[i].t - (ll)D[i].d) + L;
		A[i] = &D[i].t;
		B[i] = &D[i].d;
	}
	
	sort(A+1, A+N+1, cmpA);
	for(i = 1, j = 0, k = -1; i <= N; i++) {
		if(*A[i] != k) ++j;
		k = *A[i]; *A[i] = j;
	}
	
	sort(B+1, B+N+1, cmpA);
	for(i = 1, j = 0, k = -1; i <= N; i++) {
		if(*B[i] != k) ++j;
		k = *B[i]; *B[i] = j;
	}

	sort(D+1, D+N+1);

	for(i = 1; i <= N; i++) {
		ll val_u = TableD[D[i].d] + D[i].v;
		ll val_d = TableU[D[i].t] + D[i].v;
		TableU[D[i].t] = max(TableU[D[i].t], val_u);
		TableD[D[i].d] = max(TableD[D[i].d], val_d);
		if(res < val_u) res = val_u;
		if(res < val_d) res = val_d;
	}

	printf("%lld\n", res);

	return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6560 KB Output is correct
2 Correct 0 ms 6560 KB Output is correct
3 Correct 0 ms 6560 KB Output is correct
4 Correct 0 ms 6560 KB Output is correct
5 Correct 0 ms 6560 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 6560 KB Output is correct
2 Correct 24 ms 6560 KB Output is correct
3 Correct 52 ms 6560 KB Output is correct
4 Correct 52 ms 6560 KB Output is correct
5 Correct 64 ms 6560 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6560 KB Output is correct
2 Correct 0 ms 6560 KB Output is correct
3 Correct 0 ms 6560 KB Output is correct
4 Correct 0 ms 6560 KB Output is correct
5 Correct 0 ms 6560 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6560 KB Output is correct
2 Correct 0 ms 6560 KB Output is correct
3 Correct 0 ms 6560 KB Output is correct
4 Correct 0 ms 6560 KB Output is correct
5 Correct 0 ms 6560 KB Output is correct
6 Correct 0 ms 6560 KB Output is correct
7 Correct 0 ms 6560 KB Output is correct

Subtask #5
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6560 KB Output is correct
2 Correct 4 ms 6560 KB Output is correct
3 Correct 28 ms 6560 KB Output is correct
4 Correct 72 ms 6560 KB Output is correct
5 Correct 72 ms 6560 KB Output is correct
6 Correct 76 ms 6560 KB Output is correct
7 Correct 76 ms 6560 KB Output is correct
8 Correct 64 ms 6560 KB Output is correct
9 Correct 8 ms 6560 KB Output is correct
10 Correct 8 ms 6560 KB Output is correct
11 Correct 72 ms 6560 KB Output is correct
12 Correct 76 ms 6560 KB Output is correct