Submission #18050

#	Time	Username	Problem	Language	Result	Execution time	Memory
18050		tncks0121	OBELISK (NOI14_obelisk)	C++14	25 / 25	90 ms	1900 KiB

obelisk

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 7 / 7