제출 #1170920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170920		hamzabc	OBELISK (NOI14_obelisk)	C++20	0 / 25	11 ms	840 KiB

obelisk

#include <bits/stdc++.h>

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


long long int M, K;
vector<vector<array<long long, 3>>> holes;


long long go(long long x1, long long y1, long long x2, long long y2){
    bool k1 = abs(x1 - x2) < M + 1, k2 = abs(y1 - y2) < M + 1;
    long long oriantex, oriantey;
    oriantey = abs(y1 - y2) / (M + 1) * 2 + (abs(y1 - y2) % (M + 1));
    oriantey = min(oriantey, abs(y1 - y2) / (M + 1) * 2 + 2 + M + 1 - (abs(y1 - y2) % (M + 1)));
    if (k1 && abs(y1 - y2) % (M + 1)){
        oriantey += 2;
    }
    oriantex = abs(x1 - x2) / (M + 1) * 2 + (abs(x1 - x2) % (M + 1));
    oriantex = min(oriantex, abs(x1 - x2) / (M + 1) * 2 + 2 + M + 1 - (abs(x1 - x2) % (M + 1)));
    if (k2 && abs(x1 - x2) % (M + 1)){
        oriantex += 2;
    }
    return oriantex + oriantey;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> K >> M;
    long long bx, by, sx, sy;
    cin >> bx >> by >> sx >> sy;
    holes.resize(K - 1);
    for (int i = 0; i < K - 1; i++){
        int sk;
        cin >> sk;
        holes[i].resize(sk);
        for (int j = 0; j < sk; j++){
            cin >> holes[i][j][0] >> holes[i][j][1];
            if (i == 0)
                holes[i][j][2] = go(bx, by, holes[i][j][0], holes[i][j][1]);
        }
    }
    for (int i = 1; i < K - 1; i++){
        for (int j = holes[i].size() - 1; j >= 0; j--){
            holes[i][j][2] = LONG_MAX;
            for (int o = holes[i - 1].size() - 1; o >= 0; o--){
                holes[i][j][2] = min(holes[i][j][2], go(holes[i - 1][o][0], holes[i - 1][o][1], holes[i][j][0], holes[i][j][1]) + holes[i - 1][o][2]);
            }
        }
    }
    long long ret = LONG_MAX;
    for (int i = holes[K - 2].size() - 1; i >= 0; i--){
        ret = min(ret, holes[K - 2][i][2] + go(sx, sy, holes[K - 2][i][0], holes[K - 2][i][1]));
    }
    cout << ret;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7