oj.uz

Submission #575724

# Submission time Handle Problem Language Result Execution time Memory
575724 2022-06-11T08:27:43 Z jack715 Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 10000 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

vector<vector<int> > H, V, travel;
int R, C;

void build() {
    vector<int> presum(C);
    presum[0] = 0;
    for (int i = 0; i < C-1; i++) {
        presum[i+1] = H[0][i] + presum[i];
    }

    for (int i = 0; i < C; i++)
    for (int j = 0; j < C; j++) {
        if (i >= j)
            travel[i][j] = presum[i]-presum[j];
        else 
            travel[i][j] = presum[j]-presum[i];
    }

    for (int r = 1; r < R; r++) {
        presum[0] = 0;
        for (int i = 0; i < C-1; i++) {
            presum[i+1] = H[r][i] + presum[i];
        }

        for (int i = 0; i < C; i++) {
            vector<int> next(C, INT_MAX);
            for (int j = 0; j < C; j++) {
                for (int k = 0; k < C; k++) {
                    if (j >= k)
                        next[j] = min(next[j], travel[i][k]+presum[j]-presum[k]+V[r-1][k]);
                    else 
                        next[j] = min(next[j], travel[i][k]+presum[k]-presum[j]+V[r-1][k]);
                }
            }
            travel[i] = next;
        }
    }
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r, C = c;
    H.resize(R, vector<int>(C));
    V.resize(R, vector<int>(C));
    travel.resize(C, vector<int>(C));
    
    for (int i = 0; i < R; i++)
    for (int j = 0; j < C-1; j++)
        H[i][j] = h[i][j];
    for (int i = 0; i < R-1; i++)
    for (int j = 0; j < C; j++)
        V[i][j] = v[i][j];
    
    build();
}

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

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

int escape(int V1, int V2) {
    return travel[V1][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 94 ms 4768 KB Output is correct
2 Correct 76 ms 4780 KB Output is correct
3 Correct 134 ms 7552 KB Output is correct
4 Correct 78 ms 4692 KB Output is correct
5 Correct 75 ms 4776 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 74 ms 2692 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20096 ms 660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 8660 KB Output is correct
2 Correct 176 ms 8708 KB Output is correct
3 Correct 163 ms 8724 KB Output is correct
4 Correct 202 ms 10000 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20045 ms 660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20079 ms 652 KB Time limit exceeded
2 Halted 0 ms 0 KB -