oj.uz

Submission #1095245

# Submission time Handle Problem Language Result Execution time Memory
1095245 2024-10-01T15:53:33 Z dosts Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 85948 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[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 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);
        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]);
                }
            }
        }
    }
} 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 25432 KB Output is correct
2 Correct 10 ms 25436 KB Output is correct
3 Correct 46 ms 28204 KB Output is correct
4 Correct 10 ms 25436 KB Output is correct
5 Correct 11 ms 25512 KB Output is correct
6 Correct 1 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 600 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 452 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 1 ms 604 KB Output is correct
11 Correct 41 ms 2904 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 401 ms 1372 KB Output is correct
2 Correct 406 ms 1372 KB Output is correct
3 Correct 400 ms 1372 KB Output is correct
4 Correct 401 ms 1620 KB Output is correct
5 Correct 391 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 2009 ms 1524 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 15 ms 33628 KB Output is correct
2 Correct 14 ms 33480 KB Output is correct
3 Correct 15 ms 33628 KB Output is correct
4 Correct 37 ms 34896 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 1372 KB Output is correct
2 Correct 392 ms 1368 KB Output is correct
3 Correct 401 ms 1372 KB Output is correct
4 Correct 407 ms 1528 KB Output is correct
5 Correct 389 ms 1520 KB Output is correct
6 Correct 18 ms 33476 KB Output is correct
7 Correct 19 ms 33508 KB Output is correct
8 Correct 14 ms 33444 KB Output is correct
9 Correct 41 ms 34944 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 16 ms 25436 KB Output is correct
12 Correct 50 ms 28108 KB Output is correct
13 Correct 15 ms 25432 KB Output is correct
14 Correct 10 ms 25436 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 344 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 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 1 ms 452 KB Output is correct
25 Correct 40 ms 2780 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1985 ms 1536 KB Output is correct
28 Correct 4374 ms 59216 KB Output is correct
29 Correct 4050 ms 52688 KB Output is correct
30 Correct 4101 ms 52816 KB Output is correct
31 Correct 4404 ms 60848 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 399 ms 1536 KB Output is correct
2 Correct 392 ms 1368 KB Output is correct
3 Correct 403 ms 1372 KB Output is correct
4 Correct 403 ms 1372 KB Output is correct
5 Correct 396 ms 1520 KB Output is correct
6 Correct 14 ms 33608 KB Output is correct
7 Correct 14 ms 33372 KB Output is correct
8 Correct 15 ms 33404 KB Output is correct
9 Correct 35 ms 34824 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 13 ms 25464 KB Output is correct
12 Correct 62 ms 28188 KB Output is correct
13 Correct 11 ms 25436 KB Output is correct
14 Correct 10 ms 25564 KB Output is correct
15 Correct 2466 ms 85848 KB Output is correct
16 Execution timed out 20050 ms 85948 KB Time limit exceeded
17 Halted 0 ms 0 KB -