oj.uz

Submission #1095251

# Submission time Handle Problem Language Result Execution time Memory
1095251 2024-10-01T16:36:19 Z dosts Wombats (IOI13_wombats) C++17
28 / 100
 3233 ms 33248 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 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);
        int noyaninminikoptimizasyonununsaglayacagietki = 2*node;
        for (int i=0;i<c;i++) {
            for (int j=0;j<c;j++) {
                dp[node][i][j] = inf;
                for (int k=0;k<c;k++) {
                    dp[node][i][j] = min(dp[node][i][j],
                    dp[noyaninminikoptimizasyonununsaglayacagietki][i][k]+
                    dp[noyaninminikoptimizasyonununsaglayacagietki|1][k][j]+as[m-1][k]);
                }
            }
        }
    }

    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 = i;
            }
        }
        dnc(node,i,M,l,m-1,optl,opt);
        dnc(node,i,M,m+1,r,opt,optr);
    }
    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,0,c-1,m,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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 24920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 41 ms 3004 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 646 ms 1116 KB Output is correct
2 Correct 633 ms 1116 KB Output is correct
3 Correct 653 ms 1372 KB Output is correct
4 Correct 654 ms 1372 KB Output is correct
5 Correct 639 ms 1372 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3233 ms 1356 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 33248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 1364 KB Output is correct
2 Correct 637 ms 1116 KB Output is correct
3 Correct 655 ms 1380 KB Output is correct
4 Correct 653 ms 1372 KB Output is correct
5 Correct 642 ms 1372 KB Output is correct
6 Incorrect 66 ms 33116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 1372 KB Output is correct
2 Correct 632 ms 1344 KB Output is correct
3 Correct 653 ms 1368 KB Output is correct
4 Correct 655 ms 1372 KB Output is correct
5 Correct 639 ms 1372 KB Output is correct
6 Incorrect 62 ms 33116 KB Output isn't correct
7 Halted 0 ms 0 KB -