oj.uz

Submission #1095094

# Submission time Handle Problem Language Result Execution time Memory
1095094 2024-10-01T09:00:54 Z dosts Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 126800 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 = 25;
int N,c;
using Matrix = int[201][201];
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[1000];

    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++) {
            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[2*node][i][k]+dp[2*node+1][k][j]+as[m-1][k]);
                }
            }
        }
    }

    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++) {
            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[2*node][i][k]+dp[2*node+1][k][j]+as[m-1][k]);
                }
            }
        }   
    }
} 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 10 ms 26460 KB Output is correct
2 Correct 9 ms 26460 KB Output is correct
3 Correct 46 ms 29184 KB Output is correct
4 Correct 9 ms 26460 KB Output is correct
5 Correct 9 ms 26452 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory 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 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 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 39 ms 2896 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 297 ms 1624 KB Output is correct
2 Correct 300 ms 1628 KB Output is correct
3 Correct 305 ms 2136 KB Output is correct
4 Correct 304 ms 1864 KB Output is correct
5 Correct 304 ms 1624 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1545 ms 1804 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 34884 KB Output is correct
2 Correct 14 ms 34908 KB Output is correct
3 Correct 14 ms 34904 KB Output is correct
4 Correct 39 ms 36192 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 1856 KB Output is correct
2 Correct 302 ms 1872 KB Output is correct
3 Correct 310 ms 1624 KB Output is correct
4 Correct 322 ms 1884 KB Output is correct
5 Correct 299 ms 1880 KB Output is correct
6 Correct 19 ms 34904 KB Output is correct
7 Correct 15 ms 34908 KB Output is correct
8 Correct 16 ms 34908 KB Output is correct
9 Correct 34 ms 36180 KB Output is correct
10 Correct 11 ms 26460 KB Output is correct
11 Correct 11 ms 26460 KB Output is correct
12 Correct 49 ms 29288 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 11 ms 26460 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 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 0 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 43 ms 2920 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 1503 ms 1864 KB Output is correct
28 Correct 4152 ms 80432 KB Output is correct
29 Correct 4128 ms 74020 KB Output is correct
30 Correct 4022 ms 74068 KB Output is correct
31 Correct 4333 ms 82000 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 1840 KB Output is correct
2 Correct 300 ms 1840 KB Output is correct
3 Correct 306 ms 1884 KB Output is correct
4 Correct 304 ms 1884 KB Output is correct
5 Correct 311 ms 1856 KB Output is correct
6 Correct 16 ms 34908 KB Output is correct
7 Correct 18 ms 34904 KB Output is correct
8 Correct 16 ms 34908 KB Output is correct
9 Correct 46 ms 36176 KB Output is correct
10 Correct 14 ms 26456 KB Output is correct
11 Correct 11 ms 26460 KB Output is correct
12 Correct 60 ms 29320 KB Output is correct
13 Correct 12 ms 26460 KB Output is correct
14 Correct 11 ms 26588 KB Output is correct
15 Correct 3010 ms 126492 KB Output is correct
16 Execution timed out 20047 ms 126800 KB Time limit exceeded
17 Halted 0 ms 0 KB -