oj.uz

Submission #962173

# Submission time Handle Problem Language Result Execution time Memory
962173 2024-04-13T08:23:27 Z NValchanov Wombats (IOI13_wombats) C++17
55 / 100
 5546 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;
typedef long long ll;

const ll MAXN = 5010;
const ll MAXM = 210;
const ll INF = 4e18 + 10;

ll n,m;
ll hor[MAXN][MAXM];
ll ver[MAXN][MAXM];
ll dp[MAXN][MAXM][MAXM];

void init_dp(ll src)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            dp[i][j][src] = INF;
        }
    }

    dp[0][src][src] = 0;

    for(int j = 1; j < m; j++)
    {
        dp[0][j][src] = min(dp[0][j][src], dp[0][j - 1][src] + hor[0][j - 1]);
    }

    for(int j = m - 2; j >= 0; j--)
    {
        dp[0][j][src] = min(dp[0][j][src], dp[0][j + 1][src] + hor[0][j]);
    }
}

void fill_dp(ll src)
{
    init_dp(src);

    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            dp[i][j][src] = min(dp[i][j][src], dp[i - 1][j][src] + ver[i - 1][j]);
        }
        for(int j = 1; j < m; j++)
        {
            dp[i][j][src] = min(dp[i][j][src], dp[i][j - 1][src] + hor[i][j - 1]);
        }
        for(int j = m - 2; j >= 0; j--)
        {
            dp[i][j][src] = min(dp[i][j][src], dp[i][j + 1][src] + hor[i][j]);
        }
    }
}

void calc()
{
    for(ll src = 0; src < m; src++)
    {
        fill_dp(src);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n = R;
    m = C;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m - 1; j++)
        {
            hor[i][j] = H[i][j];
        }
    }

    for(int i = 0; i < n - 1; i++)
    {
        for(int j = 0; j < m; j++)
        {
            ver[i][j] = V[i][j];
        }
    }

    calc();
}

void changeH(int i, int j, int w) /// change path from x;y to x;y + 1
{
    hor[i][j] = w;
    calc();
}

void changeV(int i, int j, int w) /// change path from x;y to x + 1;y
{
    ver[i][j] = w;
    calc();
}

int escape(int from, int to) /// escape from (0;V1) to (N-1;V2)
{
    return dp[n - 1][to][from];
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 222312 KB Output is correct
2 Correct 123 ms 222544 KB Output is correct
3 Correct 164 ms 226132 KB Output is correct
4 Correct 118 ms 224580 KB Output is correct
5 Correct 108 ms 226520 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14680 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 56 ms 15620 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 43608 KB Output is correct
2 Correct 1159 ms 43592 KB Output is correct
3 Correct 1152 ms 43588 KB Output is correct
4 Correct 1107 ms 43612 KB Output is correct
5 Correct 1117 ms 43612 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4524 KB Output is correct
9 Correct 5546 ms 43588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 225076 KB Output is correct
2 Correct 262 ms 223044 KB Output is correct
3 Correct 254 ms 229200 KB Output is correct
4 Correct 287 ms 229712 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1152 ms 43592 KB Output is correct
2 Correct 1117 ms 43592 KB Output is correct
3 Correct 1187 ms 43612 KB Output is correct
4 Correct 1152 ms 43588 KB Output is correct
5 Correct 1114 ms 43592 KB Output is correct
6 Correct 258 ms 227080 KB Output is correct
7 Correct 278 ms 229112 KB Output is correct
8 Correct 252 ms 229112 KB Output is correct
9 Correct 283 ms 229880 KB Output is correct
10 Correct 117 ms 222552 KB Output is correct
11 Correct 117 ms 220676 KB Output is correct
12 Correct 166 ms 219904 KB Output is correct
13 Correct 111 ms 220496 KB Output is correct
14 Correct 113 ms 222564 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 2 ms 14684 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14684 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 55 ms 15704 KB Output is correct
26 Correct 2 ms 14684 KB Output is correct
27 Correct 5148 ms 43604 KB Output is correct
28 Runtime error 101 ms 262144 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 1129 ms 43592 KB Output is correct
2 Correct 1138 ms 43592 KB Output is correct
3 Correct 1174 ms 43588 KB Output is correct
4 Correct 1159 ms 43592 KB Output is correct
5 Correct 1137 ms 43600 KB Output is correct
6 Correct 257 ms 239176 KB Output is correct
7 Correct 258 ms 235152 KB Output is correct
8 Correct 256 ms 237160 KB Output is correct
9 Correct 290 ms 235724 KB Output is correct
10 Correct 107 ms 226596 KB Output is correct
11 Correct 113 ms 228628 KB Output is correct
12 Correct 166 ms 228200 KB Output is correct
13 Correct 113 ms 228432 KB Output is correct
14 Correct 113 ms 226604 KB Output is correct
15 Runtime error 170 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -