oj.uz

Submission #10383

# Submission time Handle Problem Language Result Execution time Memory
10383 2014-10-20T15:38:14 Z gs14004 OBELISK (NOI14_obelisk) C++
5 / 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);
    if(m == 1) return dx + dy;
    int pdx = 2 * (dx / (m+1));
    int pdy = 2 * (dy / (m+1));
    int ndx = (dx % (m+1));
    int ndy = (dy % (m+1));
    if(pdx == 0 && ndx) ndx+=2;
    if(pdy == 0 && ndy) ndy+=2;
    return pdx + pdy + ndx + ndy;
}

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1884 KB Output is correct
2 Correct 0 ms 1884 KB Output is correct
3 Correct 0 ms 1884 KB Output is correct
4 Correct 0 ms 1884 KB Output is correct
5 Correct 0 ms 1884 KB Output is correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1884 KB Output isn't correct
2 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 -