oj.uz

Submission #586724

# Submission time Handle Problem Language Result Execution time Memory
586724 2022-06-30T15:09:44 Z yutabi Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262144 KB 
#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;


typedef pair <int,int> ii;


vector <vector <vector <int> > > DP;

int r;
int c;

vector <vector <int> > horizontal;
vector <vector <int> > vertical;

void recalc()
{
    for(int i=0;i<c;i++)
    {
        for(int j=0;j<r;j++)
        {
            if(j==0)
            {
                for(int k=0;k<c;k++)
                {
                    DP[i][0][k]=1000000007;
                }

                DP[i][0][i]=0;
            }

            else
            {
                for(int k=0;k<c;k++)
                {
                    DP[i][j][k]=DP[i][j-1][k]+vertical[j-1][k];
                }
            }

            vector <bool> v(c,0);
            priority_queue <ii> pq;

            for(int k=0;k<c;k++)
            {
                pq.push(ii(-DP[i][j][k],k));
            }

            while(pq.size())
            {
                int ptr=pq.top().second;

                pq.pop();

                if(v[ptr])
                {
                    continue;
                }

                v[ptr]=1;

                if(ptr<c-1)
                {
                    if(DP[i][j][ptr]+horizontal[j][ptr]<DP[i][j][ptr+1])
                    {
                        DP[i][j][ptr+1]=DP[i][j][ptr]+horizontal[j][ptr];

                        pq.push(ii(-DP[i][j][ptr+1],ptr+1));
                    }
                }

                if(ptr>0)
                {
                    if(DP[i][j][ptr]+horizontal[j][ptr-1]<DP[i][j][ptr-1])
                    {
                        DP[i][j][ptr-1]=DP[i][j][ptr]+horizontal[j][ptr-1];

                        pq.push(ii(-DP[i][j][ptr-1],ptr-1));
                    }
                }
            }
        }
    }

    /*for(int i=0;i<c;i++)
    {
        for(int j=0;j<r;j++)
        {
            for(int k=0;k<c;k++)
            {
                printf("%d ",DP[i][j][k]);
            }

            printf("\n");
        }

        printf("\n");
    }*/
}


void init(int R, int C, int H[5000][200], int V[5000][200])
{
    DP=vector <vector <vector <int> > > (C,vector <vector <int> > (R,vector <int> (C)));

    r=R;
    c=C;

    horizontal=vector <vector <int> > (R,vector <int> (C-1));
    vertical=vector <vector <int> > (R-1,vector <int> (C));

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

            if(j+1!=c)
            {
                horizontal[i][j]=H[i][j];
            }
        }
    }

    recalc();
}

void changeH(int P, int Q, int W)
{
    horizontal[P][Q]=W;

    recalc();
}

void changeV(int P, int Q, int W)
{
    vertical[P][Q]=W;

    recalc();
}

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 138 ms 4820 KB Output is correct
2 Correct 142 ms 4860 KB Output is correct
3 Correct 201 ms 6432 KB Output is correct
4 Correct 133 ms 4864 KB Output is correct
5 Correct 137 ms 4864 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 66 ms 1316 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10551 ms 4820 KB Output is correct
2 Correct 7520 ms 4756 KB Output is correct
3 Correct 10557 ms 4840 KB Output is correct
4 Correct 10503 ms 4856 KB Output is correct
5 Correct 10306 ms 4804 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Execution timed out 20018 ms 4820 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 9204 KB Output is correct
2 Correct 584 ms 9172 KB Output is correct
3 Correct 535 ms 9324 KB Output is correct
4 Correct 561 ms 9912 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10389 ms 4820 KB Output is correct
2 Correct 7359 ms 4760 KB Output is correct
3 Correct 10507 ms 4848 KB Output is correct
4 Correct 10515 ms 4848 KB Output is correct
5 Correct 10233 ms 4820 KB Output is correct
6 Correct 535 ms 9292 KB Output is correct
7 Correct 569 ms 9220 KB Output is correct
8 Correct 534 ms 9216 KB Output is correct
9 Correct 555 ms 9976 KB Output is correct
10 Correct 135 ms 4868 KB Output is correct
11 Correct 134 ms 4820 KB Output is correct
12 Correct 203 ms 6424 KB Output is correct
13 Correct 134 ms 4820 KB Output is correct
14 Correct 145 ms 4860 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 62 ms 1312 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Execution timed out 20027 ms 4860 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10403 ms 4820 KB Output is correct
2 Correct 7039 ms 4756 KB Output is correct
3 Correct 10439 ms 4856 KB Output is correct
4 Correct 10498 ms 4968 KB Output is correct
5 Correct 10244 ms 4800 KB Output is correct
6 Correct 538 ms 9212 KB Output is correct
7 Correct 596 ms 9200 KB Output is correct
8 Correct 533 ms 9208 KB Output is correct
9 Correct 573 ms 9928 KB Output is correct
10 Correct 139 ms 4880 KB Output is correct
11 Correct 138 ms 4876 KB Output is correct
12 Correct 202 ms 6400 KB Output is correct
13 Correct 136 ms 4860 KB Output is correct
14 Correct 143 ms 4860 KB Output is correct
15 Runtime error 244 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -