oj.uz

Submission #1095092

# Submission time Handle Problem Language Result Execution time Memory
1095092 2024-10-01T08:57:00 Z dosts Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 86356 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 = 50;
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 11 ms 25544 KB Output is correct
2 Correct 9 ms 25548 KB Output is correct
3 Correct 48 ms 28244 KB Output is correct
4 Correct 14 ms 25436 KB Output is correct
5 Correct 9 ms 25360 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 604 KB Output is correct
8 Correct 1 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 41 ms 2892 KB Output is correct
12 Correct 0 ms 604 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 1372 KB Output is correct
2 Correct 374 ms 1372 KB Output is correct
3 Correct 363 ms 1556 KB Output is correct
4 Correct 369 ms 1372 KB Output is correct
5 Correct 367 ms 1528 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 1788 ms 1564 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Correct 11 ms 33564 KB Output is correct
3 Correct 12 ms 33628 KB Output is correct
4 Correct 31 ms 34892 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 1372 KB Output is correct
2 Correct 375 ms 1528 KB Output is correct
3 Correct 377 ms 1532 KB Output is correct
4 Correct 370 ms 1372 KB Output is correct
5 Correct 352 ms 1368 KB Output is correct
6 Correct 16 ms 33624 KB Output is correct
7 Correct 14 ms 33516 KB Output is correct
8 Correct 15 ms 33624 KB Output is correct
9 Correct 37 ms 34900 KB Output is correct
10 Correct 10 ms 25436 KB Output is correct
11 Correct 11 ms 25432 KB Output is correct
12 Correct 50 ms 28104 KB Output is correct
13 Correct 10 ms 25436 KB Output is correct
14 Correct 11 ms 25436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 476 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 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 0 ms 604 KB Output is correct
25 Correct 43 ms 2824 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1780 ms 1556 KB Output is correct
28 Correct 4166 ms 59256 KB Output is correct
29 Correct 4099 ms 52924 KB Output is correct
30 Correct 3876 ms 52768 KB Output is correct
31 Correct 4421 ms 61024 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 363 ms 1372 KB Output is correct
2 Correct 354 ms 1368 KB Output is correct
3 Correct 360 ms 1368 KB Output is correct
4 Correct 362 ms 1368 KB Output is correct
5 Correct 356 ms 1532 KB Output is correct
6 Correct 13 ms 33628 KB Output is correct
7 Correct 13 ms 33624 KB Output is correct
8 Correct 13 ms 33628 KB Output is correct
9 Correct 32 ms 34872 KB Output is correct
10 Correct 9 ms 25432 KB Output is correct
11 Correct 9 ms 25436 KB Output is correct
12 Correct 53 ms 28084 KB Output is correct
13 Correct 9 ms 25432 KB Output is correct
14 Correct 10 ms 25480 KB Output is correct
15 Correct 2210 ms 86028 KB Output is correct
16 Execution timed out 20048 ms 86356 KB Time limit exceeded
17 Halted 0 ms 0 KB -