oj.uz

Submission #1095255

# Submission time Handle Problem Language Result Execution time Memory
1095255 2024-10-01T16:41:36 Z dosts Wombats (IOI13_wombats) C++17
100 / 100
 13551 ms 66936 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include "wombats.h"
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int Q = 2e5+50,B = 100;
int N,c;
using Matrix = int[200][200];
int sag[5000][200],as[5000][2000];

Matrix d;

void man(int l,int r) {
    for (int i=0;i<c;i++) for (int j=0;j<c;j++) d[i][j] = inf;
    for (int i=0;i<c;i++) {
        d[i][i] = 0;
        for (int j=i+1;j<c;j++) d[i][j] = d[j][i] = d[i][j-1]+sag[l-1][j-1];
    }
    for (int p=l+1;p<=r;p++) {
        for (int s = 0;s<c;s++) {
            for (int j=0;j<c;j++) {
                d[s][j] = d[s][j]+as[p-2][j];
                if (j) d[s][j] = min(d[s][j],d[s][j-1]+sag[p-1][j-1]);
            }
            for (int j=c-2;j>=0;j--){
                d[s][j] = min(d[s][j],d[s][j+1]+sag[p-1][j]);
            }
        }
    } 
}

struct ST {
    Matrix dp[5000];

    void dnc(const int node,const int i,const int M,int l,int r,int optl,int optr) {
        if (l > r) return;
        int m = (l+r) >> 1;
        dp[node][i][m] = inf;
        int opt = optl;
        for (int k=optl;k<=optr;k++) {
            if (dp[2*node][i][k]+dp[2*node+1][k][m]+as[M-1][k] < dp[node][i][m]) {
                dp[node][i][m] = dp[2*node][i][k]+dp[2*node+1][k][m]+as[M-1][k];
                opt = k;
            }
        }
        dnc(node,i,M,l,m-1,optl,opt);
        dnc(node,i,M,m+1,r,opt,optr);
    }

    void build(int node,int l,int r) {
        if (l+B-1 >= r) {
            //BC^2
            man(l,r);
            for (int i=0;i<c;i++) {
                for (int j=0;j<c;j++) dp[node][i][j] = d[i][j];
            }
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m);
        build(2*node+1,m+1,r);
        for (int i=0;i<c;i++) dnc(node,i,m,0,c-1,0,c-1);
    }

    void update(int node,int l,int r,int p) {
        if (l+B-1 >= r) {
            //BC^2
            man(l,r);
            for (int i=0;i<c;i++) {
                for (int j=0;j<c;j++) dp[node][i][j] = d[i][j];
            }
            return;
        }
        int m = (l+r) >> 1;
        if  (p<=m) update(2*node,l,m,p);
        else update(2*node+1,m+1,r,p);
        for (int i=0;i<c;i++) dnc(node,i,m,0,c-1,0,c-1);
    }
} st;

void init(int32_t R, int32_t C, int32_t H[5000][200], int32_t V[5000][200]) {
    N = R,c = C;
    for (int i=0;i<N;i++) {
        for (int j=0;j<c-1;j++) sag[i][j] = H[i][j];
        if (i<N-1) for (int j=0;j<c;j++) as[i][j] = V[i][j];
    };
    st.build(1,1,N);
}

void changeH(int32_t P, int32_t Q, int32_t W) {
    sag[P][Q] = W;
    st.update(1,1,N,P+1);
}

void changeV(int32_t P, int32_t Q, int32_t W) {
    as[P][Q] = W;
    st.update(1,1,N,P+1);
}

int32_t escape(int32_t V1, int32_t V2) {
    return st.dp[1][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 9 ms 24924 KB Output is correct
2 Correct 10 ms 25012 KB Output is correct
3 Correct 58 ms 27664 KB Output is correct
4 Correct 10 ms 24920 KB Output is correct
5 Correct 9 ms 24776 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 616 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 37 ms 1544 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 1116 KB Output is correct
2 Correct 631 ms 1276 KB Output is correct
3 Correct 654 ms 1280 KB Output is correct
4 Correct 653 ms 1116 KB Output is correct
5 Correct 639 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3235 ms 1280 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32680 KB Output is correct
2 Correct 12 ms 32860 KB Output is correct
3 Correct 12 ms 32860 KB Output is correct
4 Correct 31 ms 34252 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 1268 KB Output is correct
2 Correct 638 ms 1112 KB Output is correct
3 Correct 658 ms 1280 KB Output is correct
4 Correct 655 ms 1116 KB Output is correct
5 Correct 640 ms 1112 KB Output is correct
6 Correct 14 ms 32856 KB Output is correct
7 Correct 13 ms 32860 KB Output is correct
8 Correct 13 ms 32972 KB Output is correct
9 Correct 33 ms 34128 KB Output is correct
10 Correct 9 ms 24920 KB Output is correct
11 Correct 10 ms 24924 KB Output is correct
12 Correct 44 ms 27548 KB Output is correct
13 Correct 9 ms 24920 KB Output is correct
14 Correct 13 ms 24924 KB Output is correct
15 Correct 0 ms 392 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 444 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 37 ms 2984 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 3232 ms 1372 KB Output is correct
28 Correct 3244 ms 48624 KB Output is correct
29 Correct 2705 ms 42320 KB Output is correct
30 Correct 2728 ms 42288 KB Output is correct
31 Correct 3271 ms 50260 KB Output is correct
32 Correct 0 ms 344 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 1272 KB Output is correct
2 Correct 636 ms 1268 KB Output is correct
3 Correct 654 ms 1112 KB Output is correct
4 Correct 654 ms 1116 KB Output is correct
5 Correct 643 ms 1112 KB Output is correct
6 Correct 13 ms 32860 KB Output is correct
7 Correct 13 ms 32856 KB Output is correct
8 Correct 14 ms 32860 KB Output is correct
9 Correct 33 ms 34136 KB Output is correct
10 Correct 9 ms 24924 KB Output is correct
11 Correct 9 ms 24924 KB Output is correct
12 Correct 44 ms 27648 KB Output is correct
13 Correct 9 ms 24924 KB Output is correct
14 Correct 9 ms 25016 KB Output is correct
15 Correct 1618 ms 65620 KB Output is correct
16 Correct 13544 ms 66936 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 0 ms 396 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 0 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 38 ms 2896 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 3231 ms 1376 KB Output is correct
30 Correct 3220 ms 48656 KB Output is correct
31 Correct 13480 ms 64340 KB Output is correct
32 Correct 13423 ms 64320 KB Output is correct
33 Correct 2700 ms 42324 KB Output is correct
34 Correct 11272 ms 57484 KB Output is correct
35 Correct 2705 ms 42240 KB Output is correct
36 Correct 11336 ms 57220 KB Output is correct
37 Correct 3240 ms 50396 KB Output is correct
38 Correct 13551 ms 64848 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 11595 ms 57524 KB Output is correct