Submission #4474

#	Time	Username	Problem	Language	Result	Execution time	Memory
4474		tncks0121	막대기 (KOI13_game)	C++98	100 / 100	76 ms	6560 KiB

game

#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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38