Submission #356179

#	Time	Username	Problem	Language	Result	Execution time	Memory
356179		mario05092929	Wombats (IOI13_wombats)	C++11	55 / 100	11804 ms	39732 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24