oj.uz

Submission #1036414

# Submission time Handle Problem Language Result Execution time Memory
1036414 2024-07-27T10:44:36 Z hmm789 Wombats (IOI13_wombats) C++14
28 / 100
 166 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define INF 2000000000

const int B = 2;

int h[5000][200], v[5000][200], bl[5000], br[5000], pos[5000], r, c;

struct node {
    int s, e, m;
    vector<vector<int>> f;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2;
        for(int i = 0; i < 200; i++) {
            vector<int> v(200);
            f.push_back(v);
        }
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
            merge(l->f, r->f, f);
        } else {
            build(s);
        }
    }
    void build(int s) {
        for(int i = 0; i < c; i++) {
            for(int j = i, res = 0; j < c; j++, res += h[bl[s]][j-1]) f[i][j] = res;
            for(int j = i, res = 0; j >= 0; j--, res += h[bl[s]][j]) f[i][j] = res;
            for(int j = 0; j < c; j++) f[i][j] += v[bl[s]][j];
            for(int k = bl[s]+1; k <= br[s]; k++) {
                for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j-1] + h[k][j-1]);
                for(int j = c-2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j+1] + h[k][j]);
                for(int j = 0; j < c; j++) f[i][j] += v[k][j];
            }
        }
    }
    void merge(vector<vector<int>> &a, vector<vector<int>> &b, vector<vector<int>> &f) {
        for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = INF;
        int p[c][c];
        memset(p, -1, sizeof(p));
        for(int i = 0; i < c; i++) {
            for(int j = c-1; j >= 0; j--) {
                int st = (i && p[i-1][j] != -1 ? p[i-1][j] : 0);
                int ed = (j != c-1 && p[i][j+1] != -1 ? p[i][j+1] : c-1);
                for(int k = st; k <= ed; k++) if(f[i][j] > a[i][k] + b[k][j]) {
                    f[i][j] = a[i][k] + b[k][j];
                    p[i][j] = k;
                }
            }
        }
    }
    void update(int x) {
        if(s == e) {build(s); return;}
        else if(x > m) r->update(x);
        else l->update(x);
        merge(l->f, r->f, f);
    }
} *root;

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-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];
    int cnt = (r-1)/B + 1;
    for(int i = 0; i < cnt; i++) {
        bl[i] = i*B;
        br[i] = min((i+1)*B-1, r-1);
    }
    for(int i = 0; i < cnt; i++) {
        for(int j = bl[i]; j <= br[i]; j++) pos[j] = i;
    }
    root = new node(0, cnt-1);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    root->update(pos[P]);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    root->update(pos[P]);
}

int escape(int V1, int V2) {
    return root->f[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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3508 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
11 Correct 42 ms 5992 KB Output is correct
12 Correct 2 ms 3672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 17240 KB Output is correct
2 Correct 43 ms 17244 KB Output is correct
3 Correct 53 ms 17244 KB Output is correct
4 Correct 53 ms 17240 KB Output is correct
5 Correct 53 ms 17240 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 166 ms 17188 KB Output is correct
10 Correct 1 ms 856 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 17240 KB Output is correct
2 Correct 43 ms 17244 KB Output is correct
3 Correct 53 ms 17408 KB Output is correct
4 Correct 53 ms 17240 KB Output is correct
5 Correct 54 ms 17244 KB Output is correct
6 Runtime error 110 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 17244 KB Output is correct
2 Correct 44 ms 17244 KB Output is correct
3 Correct 53 ms 17240 KB Output is correct
4 Correct 52 ms 17240 KB Output is correct
5 Correct 51 ms 17240 KB Output is correct
6 Runtime error 113 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -