oj.uz

Submission #358068

# Submission time Handle Problem Language Result Execution time Memory
358068 2021-01-25T05:52:57 Z talant117408 Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 20420 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 sum;
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];
    
    for(int i = 0; i < n-1; i++){
        sum += ver[i][0];
    }
}

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

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

int escape(int V1, int V2){
    if(m == 1){
        return sum;
    }
    else{
        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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 86 ms 9836 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 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

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 0 ms 364 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 10 ms 364 KB Output is correct
6 Correct 14 ms 364 KB Output is correct
7 Correct 27 ms 492 KB Output is correct
8 Correct 15 ms 364 KB Output is correct
9 Correct 19 ms 364 KB Output is correct
10 Correct 18 ms 364 KB Output is correct
11 Correct 8730 ms 1496 KB Output is correct
12 Correct 27 ms 364 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 876 KB Output is correct
2 Correct 233 ms 952 KB Output is correct
3 Correct 154 ms 748 KB Output is correct
4 Correct 159 ms 768 KB Output is correct
5 Correct 151 ms 812 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 242 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 615 ms 19948 KB Output is correct
2 Correct 1657 ms 20084 KB Output is correct
3 Correct 607 ms 19948 KB Output is correct
4 Execution timed out 20071 ms 20420 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 748 KB Output is correct
2 Correct 237 ms 1180 KB Output is correct
3 Correct 150 ms 748 KB Output is correct
4 Correct 147 ms 748 KB Output is correct
5 Correct 149 ms 876 KB Output is correct
6 Correct 608 ms 19948 KB Output is correct
7 Correct 1663 ms 19960 KB Output is correct
8 Correct 605 ms 20076 KB Output is correct
9 Execution timed out 20014 ms 20384 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 748 KB Output is correct
2 Correct 252 ms 1116 KB Output is correct
3 Correct 147 ms 748 KB Output is correct
4 Correct 149 ms 748 KB Output is correct
5 Correct 148 ms 748 KB Output is correct
6 Correct 641 ms 19948 KB Output is correct
7 Correct 1670 ms 20084 KB Output is correct
8 Correct 620 ms 20072 KB Output is correct
9 Execution timed out 20042 ms 20128 KB Time limit exceeded
10 Halted 0 ms 0 KB -