oj.uz

Submission #962345

# Submission time Handle Problem Language Result Execution time Memory
962345 2024-04-13T10:57:14 Z simona1230 Wombats (IOI13_wombats) C++17
55 / 100
 4425 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;

int r,c,h[5001][201],v[5001][201];
int dp[5005][205][205];
bool subt2;
bool subt3;
int tot;
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++)
        {
            h[i][j]=H[i][j];
            v[i][j]=V[i][j];
            tot+=h[i][j];
            tot+=v[i][j];
        }
    }
    if(r<=100&&c<=100||c==2)
        subt3=1;
    else if(c!=1)subt2=1;
    subt2=0;
    subt3=1;

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

        for(int k=0; k<c; k++)
            for(int i=0; i<r; i++)
            {
                for(int j=c-1; j>=0; j--)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j<c-1)dp[i][j][k]=min(dp[i][j][k],dp[i][j+1][k]+h[i][j]);
                }
                for(int j=0; j<c; j++)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j>0)dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+h[i][j-1]);
                    //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
                }
            }
}

void changeH(int x,int y,int w)
{
    tot-=h[x][y];
    h[x][y]=w;
    tot+=w;
    for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                for(int k=0; k<c; k++)
                {
                    dp[i][j][k]=1e9;
                }
                dp[0][j][j]=0;
            }
        }

        for(int k=0; k<c; k++)
            for(int i=0; i<r; i++)
            {
                for(int j=c-1; j>=0; j--)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j<c-1)dp[i][j][k]=min(dp[i][j][k],dp[i][j+1][k]+h[i][j]);
                }
                for(int j=0; j<c; j++)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j>0)dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+h[i][j-1]);
                    //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
                }
            }
}

void changeV(int x,int y,int w)
{
    tot-=v[x][y];
    v[x][y]=w;
    tot+=w;
    for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                for(int k=0; k<c; k++)
                {
                    dp[i][j][k]=1e9;
                }
                dp[0][j][j]=0;
            }
        }

        for(int k=0; k<c; k++)
            for(int i=0; i<r; i++)
            {
                for(int j=c-1; j>=0; j--)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j<c-1)dp[i][j][k]=min(dp[i][j][k],dp[i][j+1][k]+h[i][j]);
                }
                for(int j=0; j<c; j++)
                {
                    //cout<<dp[i][j][k]<<endl;
                    if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+v[i-1][j]);
                    if(j>0)dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+h[i][j-1]);
                    //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
                }
            }
}

int escape(int x,int y)
{
    if(c==1)return tot;
    return dp[r-1][y][x];
}

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;
      |      ^~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:24:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |     if(r<=100&&c<=100||c==2)
      |        ~~~~~~^~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 101756 KB Output is correct
2 Correct 92 ms 101984 KB Output is correct
3 Correct 145 ms 104512 KB Output is correct
4 Correct 90 ms 101920 KB Output is correct
5 Correct 92 ms 101968 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 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 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 54 ms 12772 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 906 ms 23472 KB Output is correct
2 Correct 881 ms 23456 KB Output is correct
3 Correct 915 ms 23472 KB Output is correct
4 Correct 899 ms 23488 KB Output is correct
5 Correct 874 ms 23468 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 4366 ms 23464 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 105820 KB Output is correct
2 Correct 199 ms 107792 KB Output is correct
3 Correct 209 ms 105820 KB Output is correct
4 Correct 238 ms 109212 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 23720 KB Output is correct
2 Correct 860 ms 23456 KB Output is correct
3 Correct 915 ms 23472 KB Output is correct
4 Correct 882 ms 23484 KB Output is correct
5 Correct 867 ms 23488 KB Output is correct
6 Correct 212 ms 103768 KB Output is correct
7 Correct 199 ms 101816 KB Output is correct
8 Correct 203 ms 103828 KB Output is correct
9 Correct 236 ms 105128 KB Output is correct
10 Correct 91 ms 99928 KB Output is correct
11 Correct 94 ms 97792 KB Output is correct
12 Correct 142 ms 102736 KB Output is correct
13 Correct 90 ms 97984 KB Output is correct
14 Correct 88 ms 99988 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 4544 KB Output is correct
18 Correct 2 ms 10588 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 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 13128 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 4425 ms 23484 KB Output is correct
28 Runtime error 164 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 869 ms 23464 KB Output is correct
2 Correct 863 ms 23456 KB Output is correct
3 Correct 892 ms 23468 KB Output is correct
4 Correct 879 ms 23464 KB Output is correct
5 Correct 884 ms 23464 KB Output is correct
6 Correct 182 ms 60092 KB Output is correct
7 Correct 218 ms 58080 KB Output is correct
8 Correct 187 ms 57944 KB Output is correct
9 Correct 227 ms 59476 KB Output is correct
10 Correct 83 ms 54024 KB Output is correct
11 Correct 81 ms 56052 KB Output is correct
12 Correct 136 ms 56676 KB Output is correct
13 Correct 104 ms 54036 KB Output is correct
14 Correct 100 ms 80068 KB Output is correct
15 Runtime error 265 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -