oj.uz

Submission #356179

# Submission time Handle Problem Language Result Execution time Memory
356179 2021-01-23T07:59:26 Z mario05092929 Wombats (IOI13_wombats) C++11
55 / 100
 11804 ms 39732 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,sum,d[80][205][205],go[80][205][205],Lmin[205],Rmin[205];
int h[5005][205],v[5005][205],kn[205][205],opt[205][205];
int d2[205][205],dist[80][205][205],sq;
int gmin[80],gmax[80],inc[5005];

void getDP(int g,int sy) {
    int st = gmin[g], en = gmax[g];
    d2[st][sy] = 0;
    for(int i = sy-1;i >= 1;i--) d2[st][i] = d2[st][i+1]+h[st][i];
    for(int i = sy+1;i <= m;i++) d2[st][i] = d2[st][i-1]+h[st][i-1];
    for(int i = st+1;i <= en;i++) {
        Lmin[1] = d2[i-1][1]+v[i-1][1], Rmin[m] = d2[i-1][m]+v[i-1][m];
        for(int j = 2;j <= m;j++) {
            Lmin[j] = min(d2[i-1][j]+v[i-1][j],Lmin[j-1]+h[i][j-1]);
        }
        for(int j = m-1;j >= 1;j--) {
            Rmin[j] = min(d2[i-1][j]+v[i-1][j],Rmin[j+1]+h[i][j]);
        }
        for(int j = 1;j <= m;j++) {
            d2[i][j] = min(Lmin[j],Rmin[j]);
        }
    }
    for(int i = 1;i <= m;i++) {
        dist[g][sy][i] = d2[en][i];
    }
}

void Knuth(int g) {
    for(int i = 1;i <= m;i++) {
        kn[m][i] = INF*2;
        for(int j = 1;j <= m;j++) {
            if(kn[m][i] > d[g][m][j]+dist[g+1][j][i]) {
                opt[m][i] = j;
                kn[m][i] = d[g][m][j]+dist[g+1][j][i];
            }
        }
    }
    for(int i = m-1;i >= 1;i--) {
        for(int j = 1;j <= m;j++) {
            kn[i][j] = INF*2;
            if(j == 1) {
                for(int k = 1;k <= m;k++) {
                    if(kn[i][j] > d[g][i][k]+dist[g+1][k][j]) {
                        opt[i][j] = k;
                        kn[i][j] = d[g][i][k]+dist[g+1][k][j];
                    }
                }
            }
            else {
                for(int k = opt[i][j-1];k <= opt[i+1][j];k++) {
                    if(kn[i][j] > d[g][i][k]+dist[g+1][k][j]) {
                        opt[i][j] = k;
                        kn[i][j] = d[g][i][k]+dist[g+1][k][j];
                    }
                }
            }
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) {
            d[g+1][i][j] = kn[i][j];
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j < m;j++) h[i][j] = H[i-1][j-1];
    }
    for(int i = 1;i < n;i++) {
        for(int j = 1;j <= m;j++) v[i][j] = V[i-1][j-1];
    }
    sq = sqrt(R);
    for(int g = 1;g <= sq;g++) {
        gmin[g] = (g-1)*sq+1;
        gmax[g] = g*sq+1;
        if(g == sq) gmax[g] = n;
        if(gmin[g] > gmax[g]) exit(-1);
        for(int i = gmin[g];i <= gmax[g];i++) inc[i] = g;
        for(int i = 1;i <= m;i++) {
            getDP(g,i);
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) {
            d[1][i][j] = dist[1][i][j];
        }
    }
    for(int g = 1;g < sq;g++) {
        Knuth(g);
    }
}

void changeH(int x, int y, int val) {
    x++, y++;
    h[x][y] = val;
    int g = inc[x];
    if(g < 1||g > sq) exit(-1);
    for(int i = 1;i <= m;i++) {
        getDP(g,i);
    }
    if(g != 1) {
        for(int i = 1;i <= m;i++) {
            getDP(g-1,i);
        }
    }
    if(g != sq) {
        for(int i = 1;i <= m;i++) {
            getDP(g+1,i);
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) {
            d[1][i][j] = dist[1][i][j];
        }
    }
    for(int gg = 1;gg < sq;gg++) {
        Knuth(gg);
    }
}

void changeV(int x, int y, int val) {
    x++, y++;
    v[x][y] = val;
    int g = inc[x];
    if(g < 1||g > sq) exit(-1);
    for(int i = 1;i <= m;i++) {
        getDP(g,i);
    }
    if(g != 1) {
        for(int i = 1;i <= m;i++) {
            getDP(g-1,i);
        }
    }
    if(g != sq) {
        for(int i = 1;i <= m;i++) {
            getDP(g+1,i);
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) {
            d[1][i][j] = dist[1][i][j];
        }
    }
    for(int gg = 1;gg < sq;gg++) {
        Knuth(gg);
    }
    
}

int escape(int sy,int ey) {
    sy++, ey++;
    return d[sq][sy][ey];
}

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;
      |      ^~~
wombats.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
wombats.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
wombats.cpp:9: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9452 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Correct 84 ms 10988 KB Output is correct
4 Correct 7 ms 9452 KB Output is correct
5 Correct 7 ms 9452 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 81 ms 1644 KB Output is correct
12 Correct 1 ms 620 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 2496 KB Output is correct
2 Correct 252 ms 2540 KB Output is correct
3 Correct 318 ms 2668 KB Output is correct
4 Correct 327 ms 2668 KB Output is correct
5 Correct 287 ms 2540 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1333 ms 2668 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17388 KB Output is correct
2 Correct 16 ms 17388 KB Output is correct
3 Correct 16 ms 17388 KB Output is correct
4 Correct 67 ms 18284 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 2412 KB Output is correct
2 Correct 228 ms 2412 KB Output is correct
3 Correct 330 ms 2668 KB Output is correct
4 Correct 314 ms 2668 KB Output is correct
5 Correct 298 ms 2540 KB Output is correct
6 Correct 16 ms 17388 KB Output is correct
7 Correct 15 ms 17388 KB Output is correct
8 Correct 16 ms 17388 KB Output is correct
9 Correct 71 ms 18284 KB Output is correct
10 Correct 7 ms 9452 KB Output is correct
11 Correct 8 ms 9452 KB Output is correct
12 Correct 86 ms 10988 KB Output is correct
13 Correct 8 ms 9452 KB Output is correct
14 Correct 8 ms 9452 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 1 ms 620 KB Output is correct
21 Correct 1 ms 620 KB Output is correct
22 Correct 1 ms 620 KB Output is correct
23 Correct 1 ms 620 KB Output is correct
24 Correct 1 ms 620 KB Output is correct
25 Correct 94 ms 1644 KB Output is correct
26 Correct 1 ms 620 KB Output is correct
27 Correct 1435 ms 2668 KB Output is correct
28 Incorrect 11804 ms 29320 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 2412 KB Output is correct
2 Correct 230 ms 2412 KB Output is correct
3 Correct 338 ms 2668 KB Output is correct
4 Correct 313 ms 2668 KB Output is correct
5 Correct 296 ms 2688 KB Output is correct
6 Correct 16 ms 17388 KB Output is correct
7 Correct 15 ms 17388 KB Output is correct
8 Correct 16 ms 17388 KB Output is correct
9 Correct 55 ms 18284 KB Output is correct
10 Correct 7 ms 9452 KB Output is correct
11 Correct 7 ms 9452 KB Output is correct
12 Correct 85 ms 10988 KB Output is correct
13 Correct 8 ms 9452 KB Output is correct
14 Correct 7 ms 9472 KB Output is correct
15 Incorrect 1920 ms 39732 KB Output isn't correct
16 Halted 0 ms 0 KB -