oj.uz

답안 #1095254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095254 2024-10-01T16:40:36 Z dosts 웜뱃 (IOI13_wombats) C++17
28 / 100
 351 ms 40284 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 = 1;
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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 28504 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 39 ms 2292 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 17376 KB Output is correct
2 Correct 90 ms 16988 KB Output is correct
3 Correct 99 ms 17496 KB Output is correct
4 Correct 97 ms 17500 KB Output is correct
5 Correct 96 ms 17244 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 351 ms 17552 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 40284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 17244 KB Output is correct
2 Correct 90 ms 17228 KB Output is correct
3 Correct 97 ms 17496 KB Output is correct
4 Correct 99 ms 17528 KB Output is correct
5 Correct 94 ms 17388 KB Output is correct
6 Runtime error 32 ms 40280 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 17376 KB Output is correct
2 Correct 88 ms 17244 KB Output is correct
3 Correct 102 ms 17492 KB Output is correct
4 Correct 102 ms 17380 KB Output is correct
5 Correct 94 ms 17388 KB Output is correct
6 Runtime error 28 ms 40224 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -