답안 #45801 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45801	2018-04-16T06:34:51 Z	TheDarkning	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	1000 ms	32012 KB

skyscraper

/**
                  ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
                  <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>

            ♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟
            ♔♕♖♗♘♙                             ♚♛♜♝♞♟
                      ˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙

**/

#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++;
      }
   }
   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[y][x] == inf )
//      assert( 0 );
      dp[y][x] = -1;

   cout << dp[y][x];
}

Compilation message

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);
       ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	31736 KB	Output is correct
2	Correct	24 ms	31784 KB	Output is correct
3	Correct	24 ms	31784 KB	Output is correct
4	Correct	25 ms	31784 KB	Output is correct
5	Correct	24 ms	31784 KB	Output is correct
6	Correct	27 ms	31784 KB	Output is correct
7	Correct	27 ms	31828 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	31828 KB	Output is correct
2	Correct	30 ms	31828 KB	Output is correct
3	Correct	26 ms	31828 KB	Output is correct
4	Correct	26 ms	31940 KB	Output is correct
5	Correct	28 ms	31940 KB	Output is correct
6	Correct	27 ms	31940 KB	Output is correct
7	Correct	26 ms	31940 KB	Output is correct
8	Correct	25 ms	31940 KB	Output is correct
9	Correct	26 ms	31940 KB	Output is correct
10	Correct	25 ms	31940 KB	Output is correct
11	Correct	27 ms	31940 KB	Output is correct
12	Correct	30 ms	31940 KB	Output is correct
13	Correct	38 ms	31940 KB	Output is correct
14	Correct	28 ms	31940 KB	Output is correct
15	Correct	36 ms	31972 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	31972 KB	Output is correct
2	Correct	26 ms	31972 KB	Output is correct
3	Correct	24 ms	31972 KB	Output is correct
4	Correct	24 ms	31972 KB	Output is correct
5	Correct	24 ms	31972 KB	Output is correct
6	Correct	24 ms	31972 KB	Output is correct
7	Correct	24 ms	31972 KB	Output is correct
8	Correct	29 ms	31972 KB	Output is correct
9	Correct	25 ms	32012 KB	Output is correct
10	Correct	29 ms	32012 KB	Output is correct
11	Correct	27 ms	32012 KB	Output is correct
12	Correct	32 ms	32012 KB	Output is correct
13	Correct	32 ms	32012 KB	Output is correct
14	Correct	30 ms	32012 KB	Output is correct
15	Correct	28 ms	32012 KB	Output is correct
16	Correct	48 ms	32012 KB	Output is correct
17	Execution timed out	1087 ms	32012 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	32012 KB	Output is correct
2	Correct	24 ms	32012 KB	Output is correct
3	Correct	23 ms	32012 KB	Output is correct
4	Correct	24 ms	32012 KB	Output is correct
5	Correct	25 ms	32012 KB	Output is correct
6	Correct	24 ms	32012 KB	Output is correct
7	Correct	28 ms	32012 KB	Output is correct
8	Correct	24 ms	32012 KB	Output is correct
9	Correct	25 ms	32012 KB	Output is correct
10	Correct	32 ms	32012 KB	Output is correct
11	Correct	29 ms	32012 KB	Output is correct
12	Correct	27 ms	32012 KB	Output is correct
13	Correct	27 ms	32012 KB	Output is correct
14	Correct	27 ms	32012 KB	Output is correct
15	Correct	36 ms	32012 KB	Output is correct
16	Correct	60 ms	32012 KB	Output is correct
17	Execution timed out	1080 ms	32012 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	32012 KB	Output is correct
2	Correct	23 ms	32012 KB	Output is correct
3	Correct	25 ms	32012 KB	Output is correct
4	Correct	26 ms	32012 KB	Output is correct
5	Correct	25 ms	32012 KB	Output is correct
6	Correct	27 ms	32012 KB	Output is correct
7	Correct	24 ms	32012 KB	Output is correct
8	Correct	25 ms	32012 KB	Output is correct
9	Correct	26 ms	32012 KB	Output is correct
10	Correct	27 ms	32012 KB	Output is correct
11	Correct	28 ms	32012 KB	Output is correct
12	Correct	34 ms	32012 KB	Output is correct
13	Correct	27 ms	32012 KB	Output is correct
14	Correct	27 ms	32012 KB	Output is correct
15	Correct	28 ms	32012 KB	Output is correct
16	Correct	48 ms	32012 KB	Output is correct
17	Execution timed out	1075 ms	32012 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #45801

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0