oj.uz

Submission #586732

# Submission time Handle Problem Language Result Execution time Memory
586732 2022-06-30T15:22:24 Z yutabi Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 9724 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(int a)
{
    for(int i=a;i==a;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];
            }
        }
    }
}

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

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

int escape(int V1, int V2)
{
    recalc(V1);
    
    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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4820 KB Output is correct
2 Correct 142 ms 4820 KB Output is correct
3 Execution timed out 20025 ms 5432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 15 ms 396 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 9 ms 400 KB Output is correct
7 Correct 10 ms 396 KB Output is correct
8 Correct 11 ms 340 KB Output is correct
9 Correct 13 ms 388 KB Output is correct
10 Correct 11 ms 396 KB Output is correct
11 Correct 6663 ms 1364 KB Output is correct
12 Correct 12 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 4820 KB Output is correct
2 Correct 76 ms 4768 KB Output is correct
3 Correct 112 ms 4844 KB Output is correct
4 Correct 117 ms 4844 KB Output is correct
5 Correct 112 ms 4692 KB Output is correct
6 Correct 1 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 Correct 91 ms 4844 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 9332 KB Output is correct
2 Correct 587 ms 9208 KB Output is correct
3 Correct 597 ms 9220 KB Output is correct
4 Execution timed out 20007 ms 9532 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 4692 KB Output is correct
2 Correct 75 ms 4764 KB Output is correct
3 Correct 114 ms 4848 KB Output is correct
4 Correct 113 ms 4852 KB Output is correct
5 Correct 109 ms 4820 KB Output is correct
6 Correct 557 ms 9332 KB Output is correct
7 Correct 594 ms 9340 KB Output is correct
8 Correct 553 ms 9296 KB Output is correct
9 Execution timed out 20015 ms 9724 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4820 KB Output is correct
2 Correct 78 ms 4764 KB Output is correct
3 Correct 117 ms 4820 KB Output is correct
4 Correct 111 ms 4820 KB Output is correct
5 Correct 113 ms 4820 KB Output is correct
6 Correct 557 ms 9200 KB Output is correct
7 Correct 587 ms 9208 KB Output is correct
8 Correct 557 ms 9212 KB Output is correct
9 Execution timed out 20081 ms 9664 KB Time limit exceeded
10 Halted 0 ms 0 KB -