oj.uz

Submission #249995

# Submission time Handle Problem Language Result Execution time Memory
249995 2020-07-16T16:14:49 Z MarcoMeijer Wombats (IOI13_wombats) C++14
100 / 100
 15809 ms 229008 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

const int MX = 6000, DIV=20;
int r, c;
int h[MX][200], v[MX][200];

int SEG[200][200][1300];
int dp[200][200][2];
int best[200][200];
int n;

void createSeg(int x, int p) {
    int bg=x*DIV;
    int ed=min(x*DIV+DIV, r);

    int m = ed-bg;

    RE(y,m) {
        bool cur=y%2;
        if(y == 0) {
            RE(i,c) RE(j,c) dp[i][j][0] = INF;
            RE(i,c) dp[i][i][0] = 0;
        } else {
            RE(i,c) RE(j,c) dp[i][j][cur] = dp[i][j][!cur]+v[bg+y-1][j];
        }
        RE(i,c) {
            REP(j,1,c  ) dp[i][j][cur] = min(dp[i][j][cur], dp[i][j-1][cur]+h[bg+y][j-1]);
            REV(j,0,c-1) dp[i][j][cur] = min(dp[i][j][cur], dp[i][j+1][cur]+h[bg+y][j]);
        }
    }
    bool cur=!(m%2);
    RE(i,c) RE(j,c) SEG[i][j][p] = dp[i][j][cur];
}
void combineSeg(int x, int p) {
    x = (x+1)*DIV-1;

    RE(i,c) RE(j,c) SEG[i][j][p] = INF;
    RE(i,c) {
        int j = 0;
        RE(k,c) {
            int val = SEG[i][k][p*2+1]+SEG[k][j][p*2+2]+v[x][k];
            if(val < SEG[i][j][p]) {
                SEG[i][j][p] = val;
                best[i][j] = k;
            }
        }
    }
    RE(j,c) {
        int i = c-1;
        RE(k,c) {
            int val = SEG[i][k][p*2+1]+SEG[k][j][p*2+2]+v[x][k];
            if(val < SEG[i][j][p]) {
                SEG[i][j][p] = val;
                best[i][j] = k;
            }
        }
    }
    REV(i,0,c-1) {
        REP(j,1,c) {
            REI(k,best[i][j-1],best[i+1][j]) {
                int val = SEG[i][k][p*2+1]+SEG[k][j][p*2+2]+v[x][k];
                if(val < SEG[i][j][p]) {
                    SEG[i][j][p] = val;
                    best[i][j] = k;
                }
            }
        }
    }
}
void buildSeg(int p=0, int l=0, int r=n-1) {
    if(l == r) {
        createSeg(l, p);
        return;
    }
    int m=(l+r)/2;
    buildSeg(p*2+1,l,m);
    buildSeg(p*2+2,m+1,r);
    combineSeg(m,p);
}
void updateSeg(int i, int p=0, int l=0, int r=n-1) {
    if(i < l || i > r) return;
    if(l == r) {
        createSeg(i,p);
        return;
    }
    int m=(l+r)/2;
    updateSeg(i,p*2+1,l,m);
    updateSeg(i,p*2+2,m+1,r);
    combineSeg(m,p);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R, c=C;
    RE(i,r) RE(j,c) h[i][j]=H[i][j]; 
    RE(i,r) RE(j,c) v[i][j]=V[i][j];
    n = (r+DIV-1)/DIV;
    buildSeg();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    updateSeg(P/DIV);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    updateSeg(P/DIV);
}

int escape(int V1, int V2) {
    return SEG[V1][V2][0];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 95 ms 14840 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Correct 8 ms 12160 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 2048 KB Output is correct
5 Correct 1 ms 2048 KB Output is correct
6 Correct 2 ms 2048 KB Output is correct
7 Correct 1 ms 2048 KB Output is correct
8 Correct 1 ms 1920 KB Output is correct
9 Correct 1 ms 2048 KB Output is correct
10 Correct 2 ms 1920 KB Output is correct
11 Correct 97 ms 4460 KB Output is correct
12 Correct 2 ms 2048 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 41464 KB Output is correct
2 Correct 355 ms 40704 KB Output is correct
3 Correct 371 ms 41464 KB Output is correct
4 Correct 363 ms 41464 KB Output is correct
5 Correct 367 ms 40824 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1629 ms 41532 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16128 KB Output is correct
2 Correct 10 ms 16128 KB Output is correct
3 Correct 11 ms 16128 KB Output is correct
4 Correct 59 ms 17400 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 41592 KB Output is correct
2 Correct 343 ms 40704 KB Output is correct
3 Correct 348 ms 41472 KB Output is correct
4 Correct 354 ms 41600 KB Output is correct
5 Correct 362 ms 40704 KB Output is correct
6 Correct 14 ms 16128 KB Output is correct
7 Correct 11 ms 16128 KB Output is correct
8 Correct 11 ms 16128 KB Output is correct
9 Correct 63 ms 17400 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 11 ms 12160 KB Output is correct
12 Correct 94 ms 14840 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 8 ms 12160 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 2048 KB Output is correct
19 Correct 1 ms 2048 KB Output is correct
20 Correct 2 ms 2048 KB Output is correct
21 Correct 1 ms 2048 KB Output is correct
22 Correct 1 ms 1920 KB Output is correct
23 Correct 1 ms 2048 KB Output is correct
24 Correct 1 ms 1920 KB Output is correct
25 Correct 92 ms 4504 KB Output is correct
26 Correct 2 ms 2048 KB Output is correct
27 Correct 1602 ms 41532 KB Output is correct
28 Correct 3242 ms 70008 KB Output is correct
29 Correct 3231 ms 68344 KB Output is correct
30 Correct 3236 ms 68344 KB Output is correct
31 Correct 3215 ms 73080 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 41472 KB Output is correct
2 Correct 337 ms 40696 KB Output is correct
3 Correct 335 ms 41372 KB Output is correct
4 Correct 333 ms 41464 KB Output is correct
5 Correct 357 ms 40704 KB Output is correct
6 Correct 11 ms 16128 KB Output is correct
7 Correct 10 ms 16128 KB Output is correct
8 Correct 11 ms 16128 KB Output is correct
9 Correct 50 ms 17400 KB Output is correct
10 Correct 7 ms 12160 KB Output is correct
11 Correct 7 ms 12160 KB Output is correct
12 Correct 102 ms 14868 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 8 ms 12160 KB Output is correct
15 Correct 2917 ms 221908 KB Output is correct
16 Correct 15809 ms 225808 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 2048 KB Output is correct
21 Correct 2 ms 2048 KB Output is correct
22 Correct 1 ms 2048 KB Output is correct
23 Correct 1 ms 2048 KB Output is correct
24 Correct 1 ms 1920 KB Output is correct
25 Correct 1 ms 2048 KB Output is correct
26 Correct 1 ms 1920 KB Output is correct
27 Correct 86 ms 4472 KB Output is correct
28 Correct 1 ms 2048 KB Output is correct
29 Correct 1605 ms 41592 KB Output is correct
30 Correct 3275 ms 71580 KB Output is correct
31 Correct 14401 ms 228452 KB Output is correct
32 Correct 14366 ms 228396 KB Output is correct
33 Correct 3580 ms 68476 KB Output is correct
34 Correct 15600 ms 225028 KB Output is correct
35 Correct 3592 ms 68552 KB Output is correct
36 Correct 15339 ms 225004 KB Output is correct
37 Correct 3494 ms 73276 KB Output is correct
38 Correct 14602 ms 229008 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 15698 ms 225120 KB Output is correct