Submission #10381

#	Time	Username	Problem	Language	Result	Execution time	Memory
10381		gs14004	OBELISK (NOI14_obelisk)	C++98	5 / 25	0 ms	1884 KiB

obelisk

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int k,m,no[505];
int ex, ey;
int vx[505][101], vy[505][101];
long long dp[505][101];

long long dist(int x, int y, int xx, int yy){
    int dx = abs(xx-x);
    int dy = abs(yy-y);
    if(m == 1) return dx + dy;
    dx = 2 * dx / (m+1) + dx % (m+1);
    dy = 2 * dy / (m+1) + dy % (m+1);
    return dx + dy + 2;
}

long long f(int pos, int ob){
    if(pos == k) return dist(vx[pos][ob],vy[pos][ob],ex,ey);
    if(dp[pos][ob]) return dp[pos][ob];
    long long res = 1e13;
    for (int i=0; i<no[pos+1]; i++) {
        res = min(res,dist(vx[pos][ob],vy[pos][ob],vx[pos+1][i],vy[pos+1][i]) + f(pos+1,i));
    }
    return dp[pos][ob] = res;
}

int main(){
    scanf("%d %d",&k,&m);
    scanf("%d %d %d %d",&ex,&ey,&vx[1][0],&vy[1][0]);
    for (int i=k; i>=2; i--) {
        scanf("%d",&no[i]);
        for (int j=0; j<no[i]; j++) {
            scanf("%d %d",&vx[i][j],&vy[i][j]);
        }
    }
    long long res = f(1,0);
    if(res >= 1e13 - 1) printf("-1");
    else printf("%lld",res);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7