Submission #1279303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279303		SnowRaven52	OBELISK (NOI14_obelisk)	C++20	25 / 25	60 ms	1084 KiB

obelisk

#include <bits/stdc++.h>
using namespace std;

long long m;

long long g(const pair<long long,long long>& a, const pair<long long,long long>& b) {
    long long inf = (1LL << 60);
    pair<long long,long long> d{ llabs(b.first - a.first), llabs(b.second - a.second) };
    if (m == 1) return d.first + d.second;
    long long vx = (d.first / (m + 1)) * (m + 1);
    long long vy = (d.second / (m + 1)) * (m + 1);
    long long best = inf;
    vector<pair<long long,long long>> c{{vx, vy}, {vx, vy + m + 1}, {vx + m + 1, vy}, {vx + m + 1, vy + m + 1}};
    for (auto p : c) {
        long long res = (p.first / (m + 1)) * 2 + (p.second / (m + 1)) * 2;
        long long dx = llabs(p.first - d.first);
        long long dy = llabs(p.second - d.second);
        res += (dx != 0 && p.second == 0) ? (2 + dx) : dx;
        res += (dy != 0 && p.first == 0) ? (2 + dy) : dy;
        best = min(best, res);
    }
    return best;
}

int main() {
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    cin >> k >> m;
    long long sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    pair<long long,long long> s{sx, sy}, e{ex, ey};

    vector<vector<pair<long long,long long>>> l(k + 1);
    l[0].push_back(s);
    for (long long i = 1; i < k; ++i) {
        long long cnt; 
        cin >> cnt;
        l[i].reserve(cnt);
        for (long long j = 0; j < cnt; ++j) {
            long long x, y; 
            cin >> x >> y;
            l[i].push_back({x, y});
        }
    }
    l[k].push_back(e);

    long long inf = (1LL << 60);
    vector<vector<long long>> dp(k + 1);
    for (long long i = 0; i <= k; ++i) dp[i].assign(l[i].size(), inf);
    dp[0][0] = 0;

    for (long long i = 0; i < k; ++i) {
        for (size_t u = 0; u < l[i].size(); ++u) {
            if (dp[i][u] >= inf) continue;
            for (size_t v = 0; v < l[i + 1].size(); ++v) {
                dp[i + 1][v] = min(dp[i + 1][v], dp[i][u] + g(l[i][u], l[i + 1][v]));
            }
        }
    }

    cout << dp[k][0] << endl;
}

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