| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4474 |
2013-10-07T16:45:56 Z |
tncks0121 |
막대기 (KOI13_game) |
C++ |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
