oj.uz

Submission #678820

# Submission time Handle Problem Language Result Execution time Memory
678820 2023-01-06T16:11:55 Z jiahng Wombats (IOI13_wombats) C++14
100 / 100
 3903 ms 112848 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];
int tmp[200][200],opt[2][200];
struct node{
    int s,e,m;
    int val[200][200];
    node *l,*r;
    bool leaf = 0;

    node(int _s,int _e){
        s = _s; e = _e; m = (s + e) / 2;

        if (e-s+1 > 20){
            l = new node(s,m); r = new node(m+1,e);
            merge();
        }else{
            leaf = 1;
            compleaf();
        }
    }
    void merge(){
        int j;
        DEC(len,C-1,1){
            FOR(i,0,C-len){ 
                j = i + len;
                val[i][j] = INF;
                int lb = (i>0?opt[(len+1)&1][i-1]:0);
                int rb = (j+1<C?opt[(len+1)&1][i]:C-1);
                FOR(k,lb,rb){
                    int res = l->val[i][k] + r->val[k][j] + V[m][k];
                    if (res < val[i][j]){
                        opt[len&1][i] = k;
                        val[i][j] = res;
                    }
                }
            }
        }
        DEC(len,C-1,0){
            FOR(i,len,C-1){ 
                j = i - len;
                val[i][j] = INF;
                int lb = (j>0?opt[(len+1)&1][i]:0);
                int rb = (i+1<C?opt[(len+1)&1][i+1]:C-1);
                FOR(k,lb,rb){
                    int res = l->val[i][k] + r->val[k][j] + V[m][k];
                    if (res < val[i][j]){
                        opt[len&1][i] = k;
                        val[i][j] = res;
                    }
                }
            }
        }
    }
        
    void updV(int row){
        if (leaf){
            compleaf(); return;
        }
        if (m < row) r->updV(row);
        else if (m > row) l->updV(row);

        merge();
    }
    void compleaf(){
        FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = abs(ss[e][i] - ss[e][j]);
        DEC(l,e-1,s){
            FOR(j,0,C-1){
                int mn = INF;
                FOR(i,0,C-1){
                    mn = min(mn, val[i][j] - ss[l][i] + V[l][i]);
                    tmp[i][j] = mn + ss[l][i];
                }
                mn = INF;
                DEC(i,C-1,0){
                    mn = min(mn, val[i][j] + ss[l][i] + V[l][i]);
                    tmp[i][j] = min(tmp[i][j], mn - ss[l][i]);
                }
            }
            FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = tmp[i][j];
        }
    }

    void updH(int row){
        if (leaf){
            compleaf();
            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 10 ms 20180 KB Output is correct
2 Correct 11 ms 20180 KB Output is correct
3 Correct 76 ms 21716 KB Output is correct
4 Correct 10 ms 20140 KB Output is correct
5 Correct 10 ms 20136 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 1 ms 340 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 64 ms 1380 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2064 KB Output is correct
2 Correct 76 ms 2096 KB Output is correct
3 Correct 81 ms 2176 KB Output is correct
4 Correct 73 ms 2132 KB Output is correct
5 Correct 75 ms 2132 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 328 ms 2156 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 13 ms 24128 KB Output is correct
2 Correct 13 ms 24148 KB Output is correct
3 Correct 12 ms 24148 KB Output is correct
4 Correct 45 ms 25544 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2004 KB Output is correct
2 Correct 69 ms 2140 KB Output is correct
3 Correct 76 ms 2164 KB Output is correct
4 Correct 72 ms 2144 KB Output is correct
5 Correct 71 ms 2132 KB Output is correct
6 Correct 12 ms 24148 KB Output is correct
7 Correct 13 ms 24128 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 45 ms 25560 KB Output is correct
10 Correct 10 ms 20180 KB Output is correct
11 Correct 12 ms 20160 KB Output is correct
12 Correct 77 ms 22940 KB Output is correct
13 Correct 10 ms 20164 KB Output is correct
14 Correct 13 ms 20156 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 436 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 444 KB Output is correct
25 Correct 69 ms 2800 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 354 ms 2144 KB Output is correct
28 Correct 923 ms 67152 KB Output is correct
29 Correct 894 ms 63396 KB Output is correct
30 Correct 880 ms 63356 KB Output is correct
31 Correct 1012 ms 68756 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2088 KB Output is correct
2 Correct 65 ms 2108 KB Output is correct
3 Correct 96 ms 2152 KB Output is correct
4 Correct 76 ms 2148 KB Output is correct
5 Correct 77 ms 2152 KB Output is correct
6 Correct 16 ms 24088 KB Output is correct
7 Correct 13 ms 24148 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 53 ms 25472 KB Output is correct
10 Correct 10 ms 20180 KB Output is correct
11 Correct 10 ms 20164 KB Output is correct
12 Correct 79 ms 22996 KB Output is correct
13 Correct 12 ms 20180 KB Output is correct
14 Correct 11 ms 20208 KB Output is correct
15 Correct 992 ms 111748 KB Output is correct
16 Correct 3738 ms 112848 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 440 KB Output is correct
24 Correct 1 ms 368 KB Output is correct
25 Correct 1 ms 436 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 74 ms 2848 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 318 ms 2156 KB Output is correct
30 Correct 900 ms 67328 KB Output is correct
31 Correct 3709 ms 110268 KB Output is correct
32 Correct 3903 ms 110332 KB Output is correct
33 Correct 973 ms 63500 KB Output is correct
34 Correct 3476 ms 106428 KB Output is correct
35 Correct 906 ms 63436 KB Output is correct
36 Correct 3272 ms 106208 KB Output is correct
37 Correct 987 ms 68876 KB Output is correct
38 Correct 3468 ms 111128 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3382 ms 106496 KB Output is correct