oj.uz

답안 #962822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962822 2024-04-14T08:38:54 Z nguyentunglam Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 4444 KB 
#include<bits/stdc++.h>
using namespace std;
#include "shortcut.h"

const int N = 3e3 + 10;

long long f[N][N];

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
  long long ans = 1e18;
    for(int x = 0; x < n; x++) for(int y = x + 1; y < n; y++) {
      for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) f[i][j] = (i == j ? 0 : 1e16);
      for(int i = 0; i + 1 < n; i++) f[i][i + 1] = f[i + 1][i] = l[i];
      f[x][y] = min(f[x][y], (long long) c);
      f[y][x] = min(f[y][x], (long long) c);
      for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
      }
      long long cost = 0;
      for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if (i != j) {
        cost = max(cost, f[i][j] + d[i] + d[j]);
//        if (f[i][j] + d[i] + d[j] == 110) {
//          cout << i << " " << j << endl;
//          cout << f[i][j] << " ";
//        }
      }
      ans = min(ans, cost);
    }
    return ans;
}

#ifdef ngu
int main()
{
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    long long t = find_shortcut(n, l, d, c);


    printf("%lld\n", t);

    return 0;
}
#endif // ngu

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 1 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 344 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 344 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 2392 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 2396 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 2396 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 344 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 344 KB n = 2, 122 is a correct answer
23 Correct 1 ms 2392 KB n = 10, 117 is a correct answer
24 Correct 1 ms 2396 KB n = 10, 336 is a correct answer
25 Correct 1 ms 2396 KB n = 10, 438 is a correct answer
26 Correct 2 ms 2500 KB n = 10, 206 is a correct answer
27 Correct 1 ms 2396 KB n = 10, 636 is a correct answer
28 Correct 0 ms 344 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 2396 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 2396 KB n = 10, 3112 is a correct answer
31 Execution timed out 2087 ms 4444 KB Time limit exceeded
32 Halted 0 ms 0 KB -