oj.uz

Submission #358277

# Submission time Handle Problem Language Result Execution time Memory
358277 2021-01-25T09:32:26 Z beksultan04 Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 20512 KB 
#include "wombats.h"
#ifndef EVAL
#include "grader.c"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define INF 1e9+7

int r[5000][200],d[5000][200],cost[5000][200],R,C;

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){
            cost[i][j] = INF;
            r[i][j] = H[i][j];
            d[i][j] = V[i][j];
        }
    /* ... */
}

void changeH(int P, int Q, int W) {
    r[P][Q] = W;
    /* ... */
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    /* ... */
}

int escape(int V1, int V2) {

    for (int i=0;i<R;++i)
        for (int j=0;j<C;++j)
            cost[i][j] = INF;


    priority_queue <pair<int,pii> > s;
    s.push({0,{0,V1}});
    cost[0][V1] = 0;
    while (!s.empty()){
        pii p = s.top().sc;
        s.pop();
        if (p.fr+1 < R){
            if (cost[p.fr+1][p.sc] > cost[p.fr][p.sc]+d[p.fr][p.sc]){

                cost[p.fr+1][p.sc] = cost[p.fr][p.sc]+d[p.fr][p.sc];
                s.push({-cost[p.fr+1][p.sc],{p.fr+1,p.sc}});

            }
        }
        if (p.sc+1 < C){
            if (cost[p.fr][p.sc+1] > cost[p.fr][p.sc]+r[p.fr][p.sc]){

                cost[p.fr][p.sc+1] = cost[p.fr][p.sc]+r[p.fr][p.sc];
                s.push({-cost[p.fr][p.sc+1],{p.fr,p.sc+1}});

            }
        }
        if (p.sc-1 >= 0){
            if (cost[p.fr][p.sc-1] > cost[p.fr][p.sc]+r[p.fr][p.sc-1]){

                cost[p.fr][p.sc-1] = cost[p.fr][p.sc]+r[p.fr][p.sc-1];
                s.push({-cost[p.fr][p.sc-1],{p.fr,p.sc-1}});

            }
        }

    }


    return cost[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 71 ms 16108 KB Output is correct
2 Correct 72 ms 16108 KB Output is correct
3 Execution timed out 20102 ms 17624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 25 ms 364 KB Output is correct
5 Correct 9 ms 364 KB Output is correct
6 Correct 12 ms 364 KB Output is correct
7 Correct 27 ms 492 KB Output is correct
8 Correct 16 ms 364 KB Output is correct
9 Correct 19 ms 364 KB Output is correct
10 Correct 16 ms 384 KB Output is correct
11 Correct 8705 ms 1728 KB Output is correct
12 Correct 26 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 876 KB Output is correct
2 Correct 250 ms 1244 KB Output is correct
3 Correct 150 ms 748 KB Output is correct
4 Correct 151 ms 748 KB Output is correct
5 Correct 153 ms 880 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 246 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 20076 KB Output is correct
2 Correct 1584 ms 19960 KB Output is correct
3 Correct 660 ms 20076 KB Output is correct
4 Execution timed out 20082 ms 20224 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 808 KB Output is correct
2 Correct 259 ms 1052 KB Output is correct
3 Correct 157 ms 748 KB Output is correct
4 Correct 150 ms 748 KB Output is correct
5 Correct 154 ms 876 KB Output is correct
6 Correct 606 ms 19948 KB Output is correct
7 Correct 1586 ms 19956 KB Output is correct
8 Correct 596 ms 20076 KB Output is correct
9 Execution timed out 20045 ms 20512 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 748 KB Output is correct
2 Correct 255 ms 952 KB Output is correct
3 Correct 160 ms 748 KB Output is correct
4 Correct 149 ms 876 KB Output is correct
5 Correct 160 ms 748 KB Output is correct
6 Correct 603 ms 19944 KB Output is correct
7 Correct 1566 ms 20076 KB Output is correct
8 Correct 600 ms 20076 KB Output is correct
9 Execution timed out 20081 ms 20192 KB Time limit exceeded
10 Halted 0 ms 0 KB -