Submission #45787

#TimeUsernameProblemLanguageResultExecution timeMemory
45787TheDarkningJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
29 ms31980 KiB
/** ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀ <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋> ♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟ ♔♕♖♗♘♙ ♚♛♜♝♞♟ ˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙ **/ #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <iomanip> #include <time.h> #include <map> #include <deque> #include <string> #include <memory.h> #include <set> #include <assert.h> #define sz(s) s.size() #define pb push_back #define fr first #define sc second #define mk make_pair #define all(s) s.begin(), s.end() using namespace std; const int N = 1e6 + 5; const int inf = 1e9 + 7; long long n, m, p, b, x, y, cnt, dp[ 2000 ][ 2000 ]; main() { scanf("%d%d", &n, &m); for( int i = 1; i < 2000; i++ ) for( int j = 1; j < 2000; j++ ) dp[ i ][ j ] = inf; for( int i = 1; i <= m; i++ ) { scanf("%d%d", &p, &b); p++; if( i == 1 ) y = p; if( i == 2 ) x = p; cnt = 0; for( int j = p; j <= n; j += b ) { dp[p][ j ] = min( dp[p][ j ], cnt ); cnt++; } cnt = 0; for( int j = p; j > 0; j -= b ) { dp[p][j] = min ( dp[p][j], cnt ); cnt++; } } // dfs( y ); for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ) for( int k = 1; k <= n; k++ ) dp[i][j] = min( dp[i][j], dp[i][k] + dp[k][j] ); for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ) for( int k = 1; k <= n; k++ ) dp[i][j] = min( dp[i][j], dp[i][k] + dp[k][j] ); for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ) for( int k = 1; k <= n; k++ ) dp[i][j] = min( dp[i][j], dp[i][k] + dp[k][j] ); if( dp[1][2] == inf ) dp[1][2] = -1; cout << dp[y][x]; }

Compilation message (stderr)

skyscraper.cpp:38:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:40:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
    scanf("%d%d", &n, &m);
                  ~~    ^
skyscraper.cpp:40:24: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
skyscraper.cpp:48:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
       scanf("%d%d", &p, &b);
                     ~~    ^
skyscraper.cpp:48:27: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
skyscraper.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &p, &b);
       ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...