Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
140374 | 梁乃元 | 抄近路 | C++ | 通过 | 100 | 2 MS | 276 KB | 722 | 2024-03-30 14:45:27 |
# include <bits/stdc++.h> using namespace std ; int x , y , n , f [1005] , lgg ; struct prk { int x , y ; void rd ( ) { cin >> x >> y ; } } p [1000005] ; bool cmp ( prk a , prk b ) { return a . y < b . y ; } int main ( ) { cin >> x >> y >> n ; for ( int i = 1 ; i <= n ; i ++ ) { p [i] . rd ( ) ; } sort ( p + 1 , p + n + 1 , cmp ) ; for ( int i = 1 ; i <= n ; i ++ ) { f [i] = 1 ; for ( int j = 1 ; j <= i ; j ++ ) { if ( p [j] . x < p [i] . x && p [j] . y < p [i] . y && f [i] < f [j] + 1 ) { f [i] = f [j] + 1 ; } } lgg = max ( lgg , f [i] ) ; } cout << int ( 100 * ( ( x + y - 2 * lgg ) + lgg * sqrt ( 2 ) ) + 0.5 ) << endl ; return 0 ; }