oj.uz

Submission #962146

# Submission time Handle Problem Language Result Execution time Memory
962146 2024-04-13T07:40:21 Z danikoynov Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 26560 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

const int maxr = 5010, maxc = 210;

void precalculate();
int h[maxr][maxc], v[maxr][maxc], dp[maxc][2][maxc];
int r, c;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    r = R;
    c = C;
    for (int i = 0; i < R - 1; i ++)
     for (int j = 0; j < C; j ++)
     v[i][j] = V[i][j];

    for (int i = 0; i < R; i ++)
     for (int j = 0; j < C - 1; j ++)
     h[i][j] = H[i][j];

     precalculate();
}

const int inf = 2e9 + 10;

void fix_row(int d, int i)
{
     for (int j = 1; j < c; j ++)
     {
          dp[d][i & 1][j] = min(dp[d][i & 1][j], dp[d][i & 1][j - 1] + h[i][j - 1]);
     }
     for (int j = c - 2; j >= 0; j --)
     {
          dp[d][i & 1][j] = min(dp[d][i & 1][j], dp[d][i & 1][j + 1] + h[i][j]);
     }
}

void calc_dp(int d)
{
     for (int i = 0; i < 2; i  ++)
          for (int j = 0; j < c; j ++)
          dp[d][i][j] = inf;

     dp[d][0][d] = 0;
     fix_row(d, 0);

     for (int i = 1; i < r; i ++)
     {
          for (int j = 0; j < c; j ++)
          {
               dp[d][i & 1][j] = dp[d][(i - 1) & 1][j] + v[i - 1][j];
          }
          fix_row(d, i);
     }
}

void precalculate()
{
     for (int d = 0; d < c; d ++)
          calc_dp(d);
}
void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q] = W;
    precalculate();
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q] = W;
    precalculate();
}

int escape(int V1, int V2)
{
     return dp[V1][(r - 1) & 1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:19:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |     for (int i = 0; i < R; i ++)
      |     ^~~
wombats.cpp:23:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |      precalculate();
      |      ^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10840 KB Output is correct
2 Correct 12 ms 10844 KB Output is correct
3 Correct 69 ms 12264 KB Output is correct
4 Correct 9 ms 10840 KB Output is correct
5 Correct 10 ms 10844 KB Output is correct
6 Correct 1 ms 2492 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 58 ms 7468 KB Output is correct
12 Correct 2 ms 6488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 6648 KB Output is correct
2 Correct 708 ms 6656 KB Output is correct
3 Correct 731 ms 6668 KB Output is correct
4 Correct 734 ms 6648 KB Output is correct
5 Correct 714 ms 6648 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 3639 ms 6652 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16832 KB Output is correct
2 Correct 56 ms 16728 KB Output is correct
3 Correct 60 ms 16824 KB Output is correct
4 Correct 84 ms 17556 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 6652 KB Output is correct
2 Correct 711 ms 6656 KB Output is correct
3 Correct 736 ms 6648 KB Output is correct
4 Correct 730 ms 6672 KB Output is correct
5 Correct 715 ms 6652 KB Output is correct
6 Correct 55 ms 16732 KB Output is correct
7 Correct 62 ms 16728 KB Output is correct
8 Correct 57 ms 16828 KB Output is correct
9 Correct 93 ms 17480 KB Output is correct
10 Correct 10 ms 10844 KB Output is correct
11 Correct 14 ms 10840 KB Output is correct
12 Correct 67 ms 12360 KB Output is correct
13 Correct 11 ms 10876 KB Output is correct
14 Correct 11 ms 10880 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 2 ms 6600 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 60 ms 7568 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 3648 ms 6668 KB Output is correct
28 Execution timed out 20087 ms 20392 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 6648 KB Output is correct
2 Correct 709 ms 6672 KB Output is correct
3 Correct 734 ms 6652 KB Output is correct
4 Correct 734 ms 6664 KB Output is correct
5 Correct 714 ms 6668 KB Output is correct
6 Correct 59 ms 16732 KB Output is correct
7 Correct 56 ms 16728 KB Output is correct
8 Correct 63 ms 16820 KB Output is correct
9 Correct 85 ms 17468 KB Output is correct
10 Correct 13 ms 10876 KB Output is correct
11 Correct 11 ms 10840 KB Output is correct
12 Correct 62 ms 12388 KB Output is correct
13 Correct 14 ms 10840 KB Output is correct
14 Correct 9 ms 10844 KB Output is correct
15 Correct 7263 ms 26560 KB Output is correct
16 Execution timed out 20024 ms 25048 KB Time limit exceeded
17 Halted 0 ms 0 KB -