oj.uz

Submission #767213

# Submission time Handle Problem Language Result Execution time Memory
767213 2023-06-26T14:03:04 Z fatemetmhr Wombats (IOI13_wombats) C++17
100 / 100
 2665 ms 109056 KB 
//  ~ Be Name Khoda ~  //

#include "wombats.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxnR =  5002;
const int maxnt =  700;
const int maxnC =  202;
const int mod   =  2e9;
const int lim   =  10;

int n, m, h[maxnR][maxnC], v[maxnR][maxnC], chil[maxnt][2];
int dp[2][maxnC][maxnC], opt[maxnC][maxnC], newnode = 1;

struct __dp{
    int dp[maxnC][maxnC];

} seg[maxnt];

inline void comb(__dp *ret, int mid, const __dp &a, const __dp &b){
    for(int dim = -(m - 1); dim < m; dim++) for(int i = max(0, -dim); i < min(m, m - dim); i++){
        int j = dim + i;
        int l = (j ? opt[i][j - 1] : 0), r = (i + 1 < m ? opt[i + 1][j] : m - 1);
        ret->dp[i][j] = mod;
        for(int k = l; k <= r; k++){
            int val = a.dp[i][k] + b.dp[k][j] + v[mid - 1][k];
            if(val < ret->dp[i][j]){
                opt[i][j] = k;
                ret->dp[i][j] = val;
            }
        }
    }
}

inline void cre(__dp *a, int l, int r){
    for(int i = 0; i < m; i++) for(int j = 0; j < m; j++)
        dp[(l + 1) & 1][i][j] = mod;
    for(int i = 0; i < m; i++)
        dp[(l + 1) & 1][i][i] = 0;
    for(int j = l; j < r; j++) for(int x = 0; x < m; x++){
        int mn = mod;
        for(int i = 0; i < m; i++){
            dp[j & 1][x][i] = min(mn, dp[(j + 1) & 1][x][i] + (j > l ? v[j - 1][i] : 0));
            mn = dp[j & 1][x][i] + h[j][i];
        }
        mn = mod;
        for(int i = m - 1; i >= 0; i--){
            dp[j & 1][x][i] = min(mn, dp[j & 1][x][i]);
            if(i)
                mn = dp[j & 1][x][i] + h[j][i - 1];
            //cout << "check " << j << ' ' << x << ' ' << i << ' ' << dp[j & 1][x][i] << ' ' << mn << endl;
        }
    }
    for(int i = 0; i < m; i++) for(int j = 0; j < m; j++)
        a->dp[i][j] = dp[(r - 1) & 1][i][j];
}

void upd(int l, int r, int id, int v){
    int mid = (l + r) >> 1;
    if(id < mid && chil[v][0])
        upd(l, mid, id, chil[v][0]);
    if(id >= mid && chil[v][1])
        upd(mid, r, id, chil[v][1]);
    if(chil[v][0] && chil[v][1])
        comb(&seg[v], mid, seg[chil[v][0]], seg[chil[v][1]]);
    else
        cre(&seg[v], l, r);
}

int build(int l, int r){
    if(r - l != n && r - l <= lim)
        return 0;
    int v = newnode++;
    assert(newnode < maxnt);
    int mid = (l + r) >> 1;
    chil[v][0] = build(l, mid);
    chil[v][1] = build(mid, r);
    if(chil[v][0] && chil[v][1])
        comb(&seg[v], mid, seg[chil[v][0]], seg[chil[v][1]]);
    else
        cre(&seg[v], l, r);
    return v;
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R;
    m = C;
    ll sum = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        h[i][j] = H[i][j];
        v[i][j] = V[i][j];
        sum += v[i][0];
    }
    build(0, n);
}

void changeH(int p, int q, int w) {
    h[p][q] = w;
    upd(0, n, p, 1);
}

void changeV(int p, int q, int w) {
    v[p][q] = w;
    upd(0, n, p, 1);
}

int escape(int v1, int v2) {
    return seg[1].dp[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 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 60 ms 17064 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 7 ms 14292 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 55 ms 1340 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 57 ms 2016 KB Output is correct
2 Correct 47 ms 2132 KB Output is correct
3 Correct 56 ms 2200 KB Output is correct
4 Correct 55 ms 2204 KB Output is correct
5 Correct 54 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 340 KB Output is correct
9 Correct 230 ms 2200 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 9 ms 18624 KB Output is correct
2 Correct 9 ms 18676 KB Output is correct
3 Correct 9 ms 18644 KB Output is correct
4 Correct 37 ms 20020 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2132 KB Output is correct
2 Correct 51 ms 2188 KB Output is correct
3 Correct 56 ms 2216 KB Output is correct
4 Correct 56 ms 2208 KB Output is correct
5 Correct 55 ms 2188 KB Output is correct
6 Correct 9 ms 18672 KB Output is correct
7 Correct 9 ms 18644 KB Output is correct
8 Correct 9 ms 18644 KB Output is correct
9 Correct 37 ms 20016 KB Output is correct
10 Correct 7 ms 14272 KB Output is correct
11 Correct 7 ms 14272 KB Output is correct
12 Correct 62 ms 17060 KB Output is correct
13 Correct 7 ms 14292 KB Output is correct
14 Correct 7 ms 14292 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 308 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 420 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 58 ms 2772 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 233 ms 2252 KB Output is correct
28 Correct 652 ms 62664 KB Output is correct
29 Correct 618 ms 59596 KB Output is correct
30 Correct 640 ms 59756 KB Output is correct
31 Correct 699 ms 64424 KB Output is correct
32 Correct 1 ms 308 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2132 KB Output is correct
2 Correct 50 ms 2132 KB Output is correct
3 Correct 56 ms 2132 KB Output is correct
4 Correct 56 ms 2204 KB Output is correct
5 Correct 55 ms 2132 KB Output is correct
6 Correct 10 ms 18644 KB Output is correct
7 Correct 9 ms 18620 KB Output is correct
8 Correct 9 ms 18644 KB Output is correct
9 Correct 37 ms 20020 KB Output is correct
10 Correct 7 ms 14292 KB Output is correct
11 Correct 6 ms 14272 KB Output is correct
12 Correct 60 ms 17136 KB Output is correct
13 Correct 7 ms 14292 KB Output is correct
14 Correct 8 ms 14292 KB Output is correct
15 Correct 732 ms 107840 KB Output is correct
16 Correct 2665 ms 109056 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 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 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 54 ms 2700 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 230 ms 2196 KB Output is correct
30 Correct 661 ms 62836 KB Output is correct
31 Correct 2466 ms 106508 KB Output is correct
32 Correct 2492 ms 106520 KB Output is correct
33 Correct 614 ms 59572 KB Output is correct
34 Correct 2349 ms 103292 KB Output is correct
35 Correct 639 ms 59540 KB Output is correct
36 Correct 2420 ms 103040 KB Output is correct
37 Correct 696 ms 64588 KB Output is correct
38 Correct 2492 ms 107100 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 2549 ms 103256 KB Output is correct