oj.uz

Submission #10377

# Submission time Handle Problem Language Result Execution time Memory
10377 2014-10-20T15:15:24 Z gs14004 OBELISK (NOI14_obelisk) C++
0 / 25
 0 ms 1884 KB 
#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);
    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 == 1) 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);
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -