Submission #18046

#	Time	Username	Problem	Language	Result	Execution time	Memory
18046		tncks0121	OBELISK (NOI14_obelisk)	C++14	5 / 25	0 ms	1636 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 roll_x = dx / (M + 1), roll_y = dy / (M + 1);
    ret = (2 * roll_x) + (2 * roll_y);
    if(dy % (M + 1) > 0) ret += dy % (M + 1) + (roll_x > 0 ? 0 : 2);
    if(dx % (M + 1) > 0) ret += dx % (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)1e12;
        }
    }

    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: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7