forked from arpitbbhayani/spoj
-
Notifications
You must be signed in to change notification settings - Fork 0
/
BRIDGE.c
94 lines (74 loc) · 1.44 KB
/
BRIDGE.c
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0
int readline ( char * str ) {
int i = 0;
char ch;
while ( (ch=getchar()) != '\n' ) {
str[i++] = ch;
}
str[i] = '\0';
return i;
}
struct node {
int a;
int b;
};
struct node array[10010];
int lis[10010];
int compar ( const void * a , const void * b ) {
struct node * x = (struct node *) a;
struct node * y = (struct node *) b;
if ( x->a == y->a ) {
return x->b - y->b;
}
return x->a - y->a;
}
int main ( int argc , char * argv[] ) {
int t , z , i , j;
scanf("%d" , &t);
for ( z = 1 ; z <= t ; z++ ) {
int n;
scanf("%d" , &n);
for ( i = 0 ; i < n ; i++ ) {
scanf("%d" , &array[i].a);
}
for ( i = 0 ; i < n ; i++ ) {
scanf("%d" , &array[i].b);
}
qsort( array , n , sizeof(struct node) , compar);
#if DEBUG
for ( i = 0 ; i < n ; i++ ) {
printf("%d " , array[i].a);
}
printf("\n");
for ( i = 0 ; i < n ; i++ ) {
printf("%d " , array[i].b);
}
printf("\n");
#endif
for ( i = 0 ; i < n ; i++ ) {
lis[i] = 1;
}
for ( i = 1 ; i < n ; i++ ) {
for ( j = 0 ; j < i ; j++ ) {
if ( array[i].b >= array[j].b && lis[i] < lis[j]+1 )
lis[i] = lis[j] + 1;
}
}
#if DEBUG
printf("LIS Table\n");
for ( i = 0 ; i < n ; i++ ) {
printf("%d " , lis[i]);
}
printf("\n");
#endif
int max = lis[0];
for ( i = 1 ; i < n ; i++ ) {
if ( lis[i] > max )
max = lis[i];
}
printf("%d\n" , max);
}
return 0;
}