oj.uz

Submission #962248

# Submission time Handle Problem Language Result Execution time Memory
962248 2024-04-13T09:41:51 Z NValchanov Wombats (IOI13_wombats) C++17
55 / 100
 5475 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];
ll ans_m1;

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;

    ans_m1 = 0;

    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];
        }
    }

    if(m == 1)
    {
        for(int i = 0; i < n; i++)
        {
            ans_m1 += ver[i][0];
        }
    }

    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
{
    if(m == 1)
    {
        ans_m1 += (w - ver[i][j]);
        ver[i][j] = w;
        return;
    }
    ver[i][j] = w;
    calc();
}

int escape(int from, int to) /// escape from (0;V1) to (N-1;V2)
{
    if(m == 1)
        return ans_m1;
    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 34 ms 86872 KB Output is correct
2 Correct 18 ms 86876 KB Output is correct
3 Correct 70 ms 88376 KB Output is correct
4 Correct 21 ms 82780 KB Output is correct
5 Correct 16 ms 86876 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 4444 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 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 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 56 ms 15564 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 1099 ms 43844 KB Output is correct
2 Correct 1020 ms 43592 KB Output is correct
3 Correct 1083 ms 43604 KB Output is correct
4 Correct 1095 ms 43608 KB Output is correct
5 Correct 1122 ms 43592 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 4444 KB Output is correct
9 Correct 5206 ms 43592 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 94124 KB Output is correct
2 Correct 281 ms 96144 KB Output is correct
3 Correct 257 ms 96148 KB Output is correct
4 Correct 305 ms 97120 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 43592 KB Output is correct
2 Correct 1051 ms 43592 KB Output is correct
3 Correct 1108 ms 43608 KB Output is correct
4 Correct 1153 ms 43588 KB Output is correct
5 Correct 1040 ms 43592 KB Output is correct
6 Correct 272 ms 106204 KB Output is correct
7 Correct 261 ms 124352 KB Output is correct
8 Correct 264 ms 124252 KB Output is correct
9 Correct 281 ms 129136 KB Output is correct
10 Correct 19 ms 119132 KB Output is correct
11 Correct 21 ms 123324 KB Output is correct
12 Correct 76 ms 133072 KB Output is correct
13 Correct 24 ms 131344 KB Output is correct
14 Correct 20 ms 131416 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 14820 KB Output is correct
19 Correct 2 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 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 2 ms 14680 KB Output is correct
25 Correct 55 ms 15576 KB Output is correct
26 Correct 2 ms 14684 KB Output is correct
27 Correct 5475 ms 43612 KB Output is correct
28 Runtime error 148 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 1082 ms 43672 KB Output is correct
2 Correct 1038 ms 43660 KB Output is correct
3 Correct 1083 ms 43672 KB Output is correct
4 Correct 1135 ms 43676 KB Output is correct
5 Correct 1067 ms 43668 KB Output is correct
6 Correct 294 ms 152400 KB Output is correct
7 Correct 279 ms 154460 KB Output is correct
8 Correct 286 ms 152432 KB Output is correct
9 Correct 325 ms 153808 KB Output is correct
10 Correct 22 ms 145488 KB Output is correct
11 Correct 23 ms 143520 KB Output is correct
12 Correct 87 ms 145772 KB Output is correct
13 Correct 23 ms 145668 KB Output is correct
14 Correct 23 ms 143448 KB Output is correct
15 Runtime error 220 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -