oj.uz

Submission #962283

# Submission time Handle Problem Language Result Execution time Memory
962283 2024-04-13T10:01:42 Z NValchanov Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 210920 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;
typedef long long ll;

const int MAXN = 5000;
const int MAXM = 100;
const int INF = 2e9 + 10;

int n,m;
int hor[MAXN][MAXM];
int ver[MAXN][MAXM];
int dp[MAXN][MAXM][MAXM];
int ans_m1;

void init_dp(int 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 fiint_dp(int 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(int src = 0; src < m; src++)
    {
        fiint_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 23 ms 205648 KB Output is correct
2 Correct 22 ms 205764 KB Output is correct
3 Correct 76 ms 207320 KB Output is correct
4 Correct 23 ms 205572 KB Output is correct
5 Correct 24 ms 205748 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 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10704 KB Output is correct
8 Correct 1 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 56 ms 11500 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 691 ms 12808 KB Output is correct
2 Correct 712 ms 13000 KB Output is correct
3 Correct 728 ms 12808 KB Output is correct
4 Correct 714 ms 12812 KB Output is correct
5 Correct 711 ms 12808 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 3574 ms 12824 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 207852 KB Output is correct
2 Correct 170 ms 207908 KB Output is correct
3 Correct 150 ms 207924 KB Output is correct
4 Correct 192 ms 208948 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 12808 KB Output is correct
2 Correct 691 ms 12820 KB Output is correct
3 Correct 700 ms 12808 KB Output is correct
4 Correct 745 ms 12808 KB Output is correct
5 Correct 710 ms 12824 KB Output is correct
6 Correct 147 ms 207856 KB Output is correct
7 Correct 146 ms 207704 KB Output is correct
8 Correct 156 ms 207696 KB Output is correct
9 Correct 196 ms 209084 KB Output is correct
10 Correct 23 ms 205652 KB Output is correct
11 Correct 25 ms 205652 KB Output is correct
12 Correct 77 ms 208144 KB Output is correct
13 Correct 25 ms 205756 KB Output is correct
14 Correct 24 ms 205648 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 1 ms 10588 KB Output is correct
24 Correct 2 ms 10584 KB Output is correct
25 Correct 58 ms 12880 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 3593 ms 12892 KB Output is correct
28 Execution timed out 20020 ms 210920 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 12808 KB Output is correct
2 Correct 692 ms 12808 KB Output is correct
3 Correct 746 ms 12888 KB Output is correct
4 Correct 705 ms 12884 KB Output is correct
5 Correct 712 ms 12828 KB Output is correct
6 Correct 156 ms 207708 KB Output is correct
7 Correct 157 ms 207852 KB Output is correct
8 Correct 147 ms 207708 KB Output is correct
9 Correct 185 ms 208644 KB Output is correct
10 Correct 26 ms 205660 KB Output is correct
11 Correct 22 ms 205648 KB Output is correct
12 Correct 80 ms 207188 KB Output is correct
13 Correct 22 ms 205652 KB Output is correct
14 Correct 22 ms 205660 KB Output is correct
15 Execution timed out 20040 ms 51904 KB Time limit exceeded
16 Halted 0 ms 0 KB -