oj.uz

Submission #358061

# Submission time Handle Problem Language Result Execution time Memory
358061 2021-01-25T05:47:15 Z talant117408 Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 20636 KB 
#include "wombats.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

int hor[5000][200], ver[5000][200], dist[5000][200];
int n, m;

bool isEligible(int x, int y){
    return x > -1 && x < n && y > -1 && y < m;
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    if(R*C > 10000) exit(0);
    n = R; m = C;
    for(int i = 0; i < n-1; i++)
        for(int j = 0; j < m; j++)
            ver[i][j] = V[i][j];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m-1; j++)
            hor[i][j] = H[i][j];
    
}

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

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

int escape(int V1, int V2) {
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dist[i][j] = 2e9;
        }
    }
    dist[0][V1] = 0;
    priority_queue <pair <int, pii>> K;
    K.push(mp(0, mp(0, V1)));
    while(!K.empty()){
        auto v = K.top().second; K.pop();
        if(isEligible(v.first, v.second-1) && dist[v.first][v.second-1] > dist[v.first][v.second]+hor[v.first][v.second-1]){
            dist[v.first][v.second-1] = dist[v.first][v.second]+hor[v.first][v.second-1];
            K.push(mp(-dist[v.first][v.second-1], mp(v.first, v.second-1)));
        }
        if(isEligible(v.first, v.second+1) && dist[v.first][v.second+1] > dist[v.first][v.second]+hor[v.first][v.second]){
            dist[v.first][v.second+1] = dist[v.first][v.second]+hor[v.first][v.second];
            K.push(mp(-dist[v.first][v.second+1], mp(v.first, v.second+1)));
        }
        if(isEligible(v.first+1, v.second) && dist[v.first+1][v.second] > dist[v.first][v.second]+ver[v.first][v.second]){
            dist[v.first+1][v.second] = dist[v.first][v.second]+ver[v.first][v.second];
            K.push(mp(-dist[v.first+1][v.second], mp(v.first+1, v.second)));
        }
    }
    return dist[n-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 74 ms 12268 KB Output is correct
2 Correct 70 ms 12140 KB Output is correct
3 Execution timed out 20036 ms 14444 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 24 ms 492 KB Output is correct
5 Correct 12 ms 492 KB Output is correct
6 Correct 15 ms 492 KB Output is correct
7 Correct 27 ms 492 KB Output is correct
8 Correct 15 ms 492 KB Output is correct
9 Correct 22 ms 492 KB Output is correct
10 Correct 17 ms 492 KB Output is correct
11 Correct 9088 ms 2804 KB Output is correct
12 Correct 38 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 888 KB Output is correct
2 Correct 296 ms 1024 KB Output is correct
3 Correct 178 ms 904 KB Output is correct
4 Correct 163 ms 876 KB Output is correct
5 Correct 153 ms 876 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 252 ms 924 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 766 ms 20076 KB Output is correct
2 Correct 1919 ms 20016 KB Output is correct
3 Correct 623 ms 20016 KB Output is correct
4 Execution timed out 20055 ms 20624 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 876 KB Output is correct
2 Correct 246 ms 1252 KB Output is correct
3 Correct 150 ms 876 KB Output is correct
4 Correct 151 ms 892 KB Output is correct
5 Correct 158 ms 876 KB Output is correct
6 Correct 620 ms 20076 KB Output is correct
7 Correct 1654 ms 20012 KB Output is correct
8 Correct 624 ms 20020 KB Output is correct
9 Execution timed out 20067 ms 20636 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 876 KB Output is correct
2 Correct 240 ms 1180 KB Output is correct
3 Correct 153 ms 876 KB Output is correct
4 Correct 153 ms 1004 KB Output is correct
5 Correct 151 ms 1136 KB Output is correct
6 Correct 606 ms 19948 KB Output is correct
7 Correct 1781 ms 20140 KB Output is correct
8 Correct 643 ms 20076 KB Output is correct
9 Execution timed out 20067 ms 20592 KB Time limit exceeded
10 Halted 0 ms 0 KB -