-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathP2439.c
More file actions
39 lines (32 loc) · 946 Bytes
/
P2439.c
File metadata and controls
39 lines (32 loc) · 946 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#define maxk 30000
struct Segment {
short start, end;
} segments[maxk];
int compare(const void *a, const void *b) {
return ((struct Segment *)a)->end - ((struct Segment *)b)->end;
}
short dp[maxk];
short max(short a, short b) {
return a > b ? a : b;
}
short len(struct Segment segment) {
return segment.end - segment.start;// + 1;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%hd %hd", &segments[i].start, &segments[i].end);
}
qsort(segments, n, sizeof(struct Segment), compare);
for (int i = 0; i < n; i++) {
dp[segments[i].end] = max(dp[segments[i].end], dp[segments[i].start] + len(segments[i]));
if (i == n - 1) break;
for (int j = segments[i].end + 1; j <= segments[i + 1].end; j++)
dp[j] = dp[segments[i].end];
}
printf("%hd\n", dp[segments[n - 1].end]);
return 0;
}