oj.uz

답안 #18050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18050 2016-01-19T08:23:53 Z tncks0121 오벨리스크 (NOI14_obelisk) C++14
25 / 25
 90 ms 1900 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)1e14;
    ll big_x = dx / (M + 1), big_y = dy / (M + 1);

    for(int px = 0; px <= 1; px++) {
        for(int py = 0; py <= 1; py++) {
            big_x += px; big_y += py;
            
            ll tmp = (2 * big_x) + (2 * big_y);

            ll small_x = dx - big_x * (M + 1);
            if(small_x < 0) small_x = -small_x;
            if(small_x > 0) 
                tmp += small_x + (big_y > 0 ? 0 : 2);

            ll small_y = dy - big_y * (M + 1);
            if(small_y < 0) small_y = -small_y;
            if(small_y > 0) 
                tmp += small_y + (big_x > 0 ? 0 : 2);

            if(tmp < ret) ret = tmp;
            big_x -= px; big_y -= py;
        }
    }
    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

# 결과 실행 시간 메모리 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
7.0 / 7.0

# 결과 실행 시간 메모리 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 3 ms 1636 KB Output is correct
5 Correct 0 ms 1636 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 1900 KB Output is correct
2 Correct 82 ms 1900 KB Output is correct
3 Correct 79 ms 1900 KB Output is correct
4 Correct 84 ms 1900 KB Output is correct
5 Correct 85 ms 1900 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 1900 KB Output is correct
2 Correct 81 ms 1900 KB Output is correct
3 Correct 79 ms 1900 KB Output is correct
4 Correct 90 ms 1900 KB Output is correct
5 Correct 85 ms 1900 KB Output is correct