Submission #10376

#	Time	Username	Problem	Language	Result	Execution time	Memory
10376		gs14004	OBELISK (NOI14_obelisk)	C++98	0 / 25	80 ms	1488 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 dist(int x, int y, int xx, int yy){
    int dx = abs(xx-x);
    int dy = abs(yy-y);
    dx = dx / (m+1) + dx % (m+1);
    dy = dy / (m+1) + dy % (m+1);
    return dx + dy + 2;
}

long long f(int pos, int ob){
    if(pos == 1) return dist(vx[pos][ob],vy[pos][ob],ex,ey);
    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 res;
}

int main(){
    scanf("%d %d",&k,&m);
    no[k] = 1;
    scanf("%d %d %d %d",&vx[k][0],&vy[k][0],&ex,&ey);
    for (int i=1; i<k; 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(k,0);
    if(res >= 1e13 - 1) printf("-1");
    else printf("%lld",res);
}

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