oj.uz

Submission #962290

# Submission time Handle Problem Language Result Execution time Memory
962290 2024-04-13T10:06:12 Z NValchanov Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 208628 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;
bool changed;

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;
    changed = true;
}

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;
    changed = true;
}

int escape(int from, int to) /// escape from (0;V1) to (N-1;V2)
{

    if(m == 1)
        return ans_m1;

    if(changed)
    {
        calc();
        changed = false;
    }
    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 29 ms 205668 KB Output is correct
2 Correct 23 ms 205656 KB Output is correct
3 Correct 75 ms 207272 KB Output is correct
4 Correct 24 ms 205792 KB Output is correct
5 Correct 24 ms 205596 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 4532 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 10584 KB Output is correct
11 Correct 57 ms 11532 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 55 ms 12832 KB Output is correct
2 Correct 430 ms 12812 KB Output is correct
3 Correct 511 ms 12808 KB Output is correct
4 Correct 507 ms 12824 KB Output is correct
5 Correct 498 ms 12828 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 196 ms 12820 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 200572 KB Output is correct
2 Correct 166 ms 200576 KB Output is correct
3 Correct 153 ms 200444 KB Output is correct
4 Correct 195 ms 205216 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12808 KB Output is correct
2 Correct 452 ms 12812 KB Output is correct
3 Correct 446 ms 12808 KB Output is correct
4 Correct 553 ms 12808 KB Output is correct
5 Correct 499 ms 12824 KB Output is correct
6 Correct 152 ms 204120 KB Output is correct
7 Correct 171 ms 204216 KB Output is correct
8 Correct 152 ms 207860 KB Output is correct
9 Correct 170 ms 208628 KB Output is correct
10 Correct 29 ms 205580 KB Output is correct
11 Correct 24 ms 205748 KB Output is correct
12 Correct 79 ms 207292 KB Output is correct
13 Correct 26 ms 205660 KB Output is correct
14 Correct 22 ms 189216 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 10584 KB Output is correct
19 Correct 2 ms 10584 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 2 ms 10584 KB Output is correct
23 Correct 2 ms 10584 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 57 ms 11564 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 210 ms 12636 KB Output is correct
28 Execution timed out 20047 ms 207872 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12900 KB Output is correct
2 Correct 423 ms 12872 KB Output is correct
3 Correct 470 ms 12892 KB Output is correct
4 Correct 503 ms 12892 KB Output is correct
5 Correct 490 ms 12888 KB Output is correct
6 Correct 152 ms 207932 KB Output is correct
7 Correct 165 ms 204116 KB Output is correct
8 Correct 155 ms 206104 KB Output is correct
9 Correct 190 ms 207376 KB Output is correct
10 Correct 24 ms 205676 KB Output is correct
11 Correct 23 ms 203952 KB Output is correct
12 Correct 81 ms 206400 KB Output is correct
13 Correct 23 ms 205660 KB Output is correct
14 Correct 26 ms 205656 KB Output is correct
15 Incorrect 19850 ms 57036 KB Output isn't correct
16 Halted 0 ms 0 KB -