oj.uz

Submission #962313

# Submission time Handle Problem Language Result Execution time Memory
962313 2024-04-13T10:27:00 Z Ice_man Wombats (IOI13_wombats) C++14
55 / 100
 3975 ms 262144 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include "wombats.h"
#include <bits/stdc++.h>

#define maxn 5005
#define maxn2 205


using namespace std;

int c, r;
int h[maxn][maxn2];
int v[maxn][maxn2];




int dp[205][5005][205];



void calc_row(int i, int j)
{
    for(int k = 1; k < c; k++)
        dp[i][j][k] = min(dp[i][j][k], dp[i][j][k - 1] + h[j][k - 1]);

    for(int k = c - 2; k > -1; k--)
        dp[i][j][k] = min(dp[i][j][k], dp[i][j][k + 1] + h[j][k]);
}



void calc_dp(int i)
{
    for(int j = 0; j < r; j++)
        for(int k = 0; k < c; k++)
            dp[i][j][k] = 2 * 1e9;
    dp[i][0][i] = 0;

    calc_row(i, 0);


    for(int j = 1; j < r; j++)
    {
        for(int k = 0; k < c; k++)
            dp[i][j][k] = dp[i][j - 1][k] + v[j - 1][k];
        calc_row(i, j);
    }
}



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


    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
        {
            if(i + 1 < r)
                v[i][j] = V[i][j];
            if(j + 1 < c)
                h[i][j] = H[i][j];
        }

    for(int i = 0; i < c; i++)
        calc_dp(i);
}



void changeH(int P , int Q , int W)
{
    h[P][Q] = W;
    for(int i = 0; i < c; i++)
        calc_dp(i);
}


void changeV(int P , int Q , int W)
{
    v[P][Q] = W;
    for(int i = 0; i < c; i++)
        calc_dp(i);
}


int escape(int V1 , int V2)
{
    return dp[V1][r - 1][V2];
}

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 16 ms 16988 KB Output is correct
2 Correct 18 ms 16988 KB Output is correct
3 Correct 68 ms 18492 KB Output is correct
4 Correct 18 ms 16984 KB Output is correct
5 Correct 15 ms 16984 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 4696 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 24 ms 49496 KB Output is correct
5 Correct 7 ms 49688 KB Output is correct
6 Correct 6 ms 49500 KB Output is correct
7 Correct 6 ms 49496 KB Output is correct
8 Correct 6 ms 47448 KB Output is correct
9 Correct 6 ms 49500 KB Output is correct
10 Correct 6 ms 47452 KB Output is correct
11 Correct 67 ms 51504 KB Output is correct
12 Correct 6 ms 49496 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 220060 KB Output is correct
2 Correct 808 ms 218076 KB Output is correct
3 Correct 825 ms 220144 KB Output is correct
4 Correct 821 ms 220144 KB Output is correct
5 Correct 793 ms 217936 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4544 KB Output is correct
9 Correct 3929 ms 220136 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 26716 KB Output is correct
2 Correct 72 ms 26972 KB Output is correct
3 Correct 77 ms 26984 KB Output is correct
4 Correct 99 ms 28104 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 220060 KB Output is correct
2 Correct 803 ms 218284 KB Output is correct
3 Correct 814 ms 220140 KB Output is correct
4 Correct 816 ms 220148 KB Output is correct
5 Correct 777 ms 217940 KB Output is correct
6 Correct 73 ms 26972 KB Output is correct
7 Correct 74 ms 26972 KB Output is correct
8 Correct 73 ms 26972 KB Output is correct
9 Correct 102 ms 27984 KB Output is correct
10 Correct 15 ms 16984 KB Output is correct
11 Correct 20 ms 16988 KB Output is correct
12 Correct 68 ms 19516 KB Output is correct
13 Correct 14 ms 17064 KB Output is correct
14 Correct 19 ms 17036 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 6 ms 49496 KB Output is correct
19 Correct 6 ms 49500 KB Output is correct
20 Correct 6 ms 49500 KB Output is correct
21 Correct 6 ms 49500 KB Output is correct
22 Correct 6 ms 47448 KB Output is correct
23 Correct 6 ms 49500 KB Output is correct
24 Correct 6 ms 47452 KB Output is correct
25 Correct 60 ms 51796 KB Output is correct
26 Correct 6 ms 49500 KB Output is correct
27 Correct 3975 ms 220140 KB Output is correct
28 Runtime error 355 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 796 ms 220060 KB Output is correct
2 Correct 810 ms 218080 KB Output is correct
3 Correct 807 ms 220252 KB Output is correct
4 Correct 835 ms 220144 KB Output is correct
5 Correct 824 ms 218096 KB Output is correct
6 Correct 87 ms 26972 KB Output is correct
7 Correct 75 ms 26968 KB Output is correct
8 Correct 77 ms 26980 KB Output is correct
9 Correct 106 ms 28140 KB Output is correct
10 Correct 19 ms 17056 KB Output is correct
11 Correct 15 ms 16984 KB Output is correct
12 Correct 74 ms 19400 KB Output is correct
13 Correct 14 ms 16988 KB Output is correct
14 Correct 21 ms 16988 KB Output is correct
15 Runtime error 621 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -