oj.uz

Submission #962140

# Submission time Handle Problem Language Result Execution time Memory
962140 2024-04-13T07:36:16 Z danikoynov Wombats (IOI13_wombats) C++14
55 / 100
 3988 ms 262148 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][maxr][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][j] = min(dp[d][i][j], dp[d][i][j - 1] + h[i][j - 1]);
     }
     for (int j = c - 2; j >= 0; j --)
     {
          dp[d][i][j] = min(dp[d][i][j], dp[d][i][j + 1] + h[i][j]);
     }
}

void calc_dp(int d)
{
     for (int i = 0; i < r;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][j] = dp[d][i - 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][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 13 ms 16988 KB Output is correct
2 Correct 14 ms 16988 KB Output is correct
3 Correct 68 ms 19664 KB Output is correct
4 Correct 14 ms 16984 KB Output is correct
5 Correct 14 ms 16984 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 6 ms 47452 KB Output is correct
5 Correct 6 ms 47452 KB Output is correct
6 Correct 5 ms 47452 KB Output is correct
7 Correct 5 ms 47448 KB Output is correct
8 Correct 6 ms 45404 KB Output is correct
9 Correct 5 ms 47452 KB Output is correct
10 Correct 5 ms 45404 KB Output is correct
11 Correct 65 ms 48664 KB Output is correct
12 Correct 5 ms 47448 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 163308 KB Output is correct
2 Correct 770 ms 161252 KB Output is correct
3 Correct 794 ms 161360 KB Output is correct
4 Correct 811 ms 159580 KB Output is correct
5 Correct 795 ms 157248 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 3982 ms 157440 KB Output is correct
10 Correct 6 ms 14680 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 25436 KB Output is correct
2 Correct 69 ms 25580 KB Output is correct
3 Correct 73 ms 25436 KB Output is correct
4 Correct 95 ms 26876 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 157408 KB Output is correct
2 Correct 792 ms 159288 KB Output is correct
3 Correct 816 ms 159568 KB Output is correct
4 Correct 809 ms 157264 KB Output is correct
5 Correct 813 ms 157352 KB Output is correct
6 Correct 68 ms 25524 KB Output is correct
7 Correct 65 ms 25436 KB Output is correct
8 Correct 68 ms 25612 KB Output is correct
9 Correct 93 ms 26852 KB Output is correct
10 Correct 13 ms 17056 KB Output is correct
11 Correct 16 ms 16988 KB Output is correct
12 Correct 70 ms 19592 KB Output is correct
13 Correct 12 ms 16988 KB Output is correct
14 Correct 13 ms 17064 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4540 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 5 ms 47596 KB Output is correct
19 Correct 6 ms 47452 KB Output is correct
20 Correct 6 ms 47452 KB Output is correct
21 Correct 6 ms 47448 KB Output is correct
22 Correct 5 ms 45400 KB Output is correct
23 Correct 5 ms 47452 KB Output is correct
24 Correct 5 ms 45576 KB Output is correct
25 Correct 64 ms 49852 KB Output is correct
26 Correct 6 ms 47452 KB Output is correct
27 Correct 3988 ms 155552 KB Output is correct
28 Runtime error 416 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 188764 KB Output is correct
2 Correct 799 ms 216228 KB Output is correct
3 Correct 817 ms 220244 KB Output is correct
4 Correct 803 ms 220496 KB Output is correct
5 Correct 795 ms 219984 KB Output is correct
6 Correct 63 ms 25688 KB Output is correct
7 Correct 66 ms 25436 KB Output is correct
8 Correct 67 ms 25608 KB Output is correct
9 Correct 101 ms 26784 KB Output is correct
10 Correct 14 ms 16988 KB Output is correct
11 Correct 14 ms 16988 KB Output is correct
12 Correct 67 ms 19632 KB Output is correct
13 Correct 12 ms 16988 KB Output is correct
14 Correct 14 ms 17064 KB Output is correct
15 Runtime error 620 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -