oj.uz

Submission #18049

# Submission time Handle Problem Language Result Execution time Memory
18049 2016-01-19T08:11:40 Z tncks0121 OBELISK (NOI14_obelisk) C++14
5 / 25
 1 ms 1636 KB 
#define _CRT_SECURE_NO_WARNINGS
       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
const int K_ = 505;

int K, M;
int sx, sy, ex, ey;

vector< tuple<int, int> > holes[K_];
ll tb[K_][105];

ll dist (ll dx, ll dy) {
    if(dx < 0) dx = -dx;
    if(dy < 0) dy = -dy;
    // 세로로 세운 (0,0)에서 세로로 세운 (dx, dy)까지 몇 번을 굴려야 하는가?

    // 한칸짜리 : 자명
    if(M == 1) return dx + dy;
    
    // 그외: 어쩌지?
    ll ret;
    ll roll_x = dx / (M + 1), roll_y = dy / (M + 1);
    ret = (2 * roll_x) + (2 * roll_y);
    if(dy % (M + 1) > 0) 
        ret += min(dy % (M + 1), 2 + (M+1) - dy % (M+1)) + (roll_x > 0 ? 0 : 2);
    if(dx % (M + 1) > 0) 
        ret += min(dx % (M + 1), 2 + (M+1) - dy % (M+1)) + (roll_y > 0 ? 0 : 2);
    return ret;
}

int main() {
    scanf("%d%d", &K, &M);

    {
        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        holes[K-1].push_back( tie(ex, ey) );
    }

    for(int i = 0; i+1 < K; i++) {
        int h; scanf("%d", &h);
        while(h--) {
            int x, y; scanf("%d%d", &x, &y);
            holes[i].push_back( tie(x, y) );
        }
    }

    { // init
        for(int i = 0; i < holes[0].size(); i++) {
            int xi, yi; tie(xi, yi) = holes[0][i];
            tb[0][i] = dist(xi - sx, yi - sy);
        }
        for(int f = 1; f < K; f++) {
            for(int i = 0; i < holes[f].size(); i++) tb[f][i] = (ll)1e13;
        }
    }

    for(int f = 0; f+1 < K; f++) {
        for(int i = 0; i < holes[f].size(); i++) {
            int xi, yi; tie(xi, yi) = holes[f][i];
            for(int j = 0; j < holes[f+1].size(); j++) {
                int xj, yj; tie(xj, yj) = holes[f+1][j];
                tb[f+1][j] = min(tb[f+1][j], tb[f][i] + dist(xi - xj, yi - yj));
            }
        }
    }

    printf("%lld\n", tb[K-1][0]);


    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 7.0

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