oj.uz

Submission #678710

# Submission time Handle Problem Language Result Execution time Memory
678710 2023-01-06T11:46:55 Z jiahng Wombats (IOI13_wombats) C++14
55 / 100
 806 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int R,C;
int H[5000][200], V[5000][200], ss[5000][200];
struct node{
    int s,e,m;
    int val[200][200];
    node *l,*r;
    
    node(int _s,int _e){
        s = _s; e = _e; m = (s + e) / 2;
        if (s != e){
            l = new node(s,m); r = new node(m+1,e);
            merge();
        }else{
            FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = abs(ss[s][i] - ss[s][j]);
        }
    }
    void merge(){
        FOR(j,0,C-1) merge_one(0,C-1,0,C-1,j);
    }
    void merge_one(int a,int b,int vl,int vr, int j){
        if (a > b) return;
        int c = (a + b) / 2;

        int opt = -1;
        val[c][j] = INF;
        FOR(k,vl,vr){
            int res = l->val[c][k] + r->val[k][j] + V[m][k];
            if (res < val[c][j]){
                opt = k; val[c][j] = res;
            }
        }
        merge_one(a,c-1,vl,opt,j);
        merge_one(c+1,b,opt,vr,j);
    }

    void updV(int row){
        if (m < row) r->updV(row);
        else if (m > row) l->updV(row);

        merge();
    }
    void updH(int row){
        if (s == e){
            FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = abs(ss[s][i] - ss[s][j]);
            return;
        }
        if (row > m) r->updH(row);
        else l->updH(row);
        merge();
    }
}*root;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R = R; ::C = C;
    FOR(i,0,R-1) FOR(j,0,C-1){
        ::H[i][j] = H[i][j];
        ::V[i][j] = V[i][j];
    }
    FOR(i,0,R-1){
        ss[i][0] = 0;
        
        FOR(j,1,C-1){
            ss[i][j] = ss[i][j-1] + H[i][j-1];
        }
    }
    root = new node(0,R-1);

    /*
    FOR(i,0,C-1){
        FOR(j,0,C-1) cout << root->val[i][j] << ' ';
        cout << '\n';
    }
    */
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W; 
    FOR(j,1,C-1) ss[P][j] = ss[P][j-1] + H[P][j-1];

    root->updH(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    root->updV(P);
}

int escape(int V1, int V2) {
    return root->val[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 39 ms 79052 KB Output is correct
2 Correct 37 ms 78996 KB Output is correct
3 Correct 101 ms 80588 KB Output is correct
4 Correct 41 ms 79000 KB Output is correct
5 Correct 36 ms 78972 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 67 ms 2000 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 16880 KB Output is correct
2 Correct 124 ms 16940 KB Output is correct
3 Correct 188 ms 17108 KB Output is correct
4 Correct 160 ms 17096 KB Output is correct
5 Correct 171 ms 17188 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 566 ms 17220 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 82976 KB Output is correct
2 Correct 41 ms 82872 KB Output is correct
3 Correct 41 ms 82912 KB Output is correct
4 Correct 75 ms 83736 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 16820 KB Output is correct
2 Correct 128 ms 16928 KB Output is correct
3 Correct 179 ms 17068 KB Output is correct
4 Correct 160 ms 17108 KB Output is correct
5 Correct 162 ms 16972 KB Output is correct
6 Correct 38 ms 83020 KB Output is correct
7 Correct 40 ms 82888 KB Output is correct
8 Correct 42 ms 82916 KB Output is correct
9 Correct 72 ms 83792 KB Output is correct
10 Correct 37 ms 78960 KB Output is correct
11 Correct 36 ms 79076 KB Output is correct
12 Correct 100 ms 80592 KB Output is correct
13 Correct 36 ms 79040 KB Output is correct
14 Correct 35 ms 79012 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 1 ms 980 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 66 ms 2024 KB Output is correct
26 Correct 1 ms 1108 KB Output is correct
27 Correct 567 ms 17108 KB Output is correct
28 Runtime error 419 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 16856 KB Output is correct
2 Correct 121 ms 16896 KB Output is correct
3 Correct 176 ms 17048 KB Output is correct
4 Correct 165 ms 16972 KB Output is correct
5 Correct 166 ms 17096 KB Output is correct
6 Correct 40 ms 82900 KB Output is correct
7 Correct 39 ms 82932 KB Output is correct
8 Correct 41 ms 82876 KB Output is correct
9 Correct 72 ms 83780 KB Output is correct
10 Correct 36 ms 79052 KB Output is correct
11 Correct 36 ms 78972 KB Output is correct
12 Correct 100 ms 80664 KB Output is correct
13 Correct 37 ms 79052 KB Output is correct
14 Correct 37 ms 79016 KB Output is correct
15 Runtime error 806 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -