oj.uz

Submission #962275

# Submission time Handle Problem Language Result Execution time Memory
962275 2024-04-13T09:57:53 Z NValchanov Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;
typedef long long ll;

const ll MAXN = 5000;
const ll MAXM = 100;
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 71 ms 179240 KB Output is correct
2 Correct 23 ms 181072 KB Output is correct
3 Correct 75 ms 181840 KB Output is correct
4 Correct 23 ms 181076 KB Output is correct
5 Correct 23 ms 179292 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 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 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 66 ms 11604 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 16920 KB Output is correct
2 Correct 750 ms 16916 KB Output is correct
3 Correct 748 ms 16980 KB Output is correct
4 Correct 749 ms 16920 KB Output is correct
5 Correct 756 ms 16916 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
9 Correct 3583 ms 16912 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 177032 KB Output is correct
2 Correct 205 ms 182952 KB Output is correct
3 Correct 189 ms 184660 KB Output is correct
4 Correct 226 ms 184148 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 16912 KB Output is correct
2 Correct 743 ms 16916 KB Output is correct
3 Correct 798 ms 16912 KB Output is correct
4 Correct 787 ms 16920 KB Output is correct
5 Correct 742 ms 16920 KB Output is correct
6 Correct 189 ms 184668 KB Output is correct
7 Correct 203 ms 182724 KB Output is correct
8 Correct 186 ms 182872 KB Output is correct
9 Correct 235 ms 185972 KB Output is correct
10 Correct 23 ms 179292 KB Output is correct
11 Correct 23 ms 181168 KB Output is correct
12 Correct 77 ms 183420 KB Output is correct
13 Correct 23 ms 179184 KB Output is correct
14 Correct 25 ms 181104 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 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 2 ms 10588 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 61 ms 12584 KB Output is correct
26 Correct 2 ms 10584 KB Output is correct
27 Correct 3770 ms 17008 KB Output is correct
28 Runtime error 124 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 789 ms 16992 KB Output is correct
2 Correct 765 ms 16988 KB Output is correct
3 Correct 806 ms 16996 KB Output is correct
4 Correct 760 ms 16848 KB Output is correct
5 Correct 780 ms 17000 KB Output is correct
6 Correct 233 ms 186716 KB Output is correct
7 Correct 213 ms 186688 KB Output is correct
8 Correct 224 ms 188468 KB Output is correct
9 Correct 254 ms 189748 KB Output is correct
10 Correct 25 ms 183120 KB Output is correct
11 Correct 27 ms 185180 KB Output is correct
12 Correct 79 ms 187572 KB Output is correct
13 Correct 25 ms 183124 KB Output is correct
14 Correct 24 ms 183132 KB Output is correct
15 Execution timed out 20017 ms 105536 KB Time limit exceeded
16 Halted 0 ms 0 KB -