제출 #1328124

#제출 시각아이디문제언어결과실행 시간메모리
1328124model_codeAmbulance (JOI25_ambulance)C++20
100 / 100
1114 ms32012 KiB
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;

bool chmin(int &x, int y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, n, t;
    cin >> l >> n >> t;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        --x[i];
        --y[i];
    }

    t /= 2;
    array<pair<int, int>, 4> hsp;
    hsp[0] = pair<int, int>(0, 0);
    hsp[1] = pair<int, int>(0, l - 1);
    hsp[2] = pair<int, int>(l - 1, l - 1);
    hsp[3] = pair<int, int>(l - 1, 0);
    auto dist = [&](int hid, int pid) -> int {
        auto [x_, y_] = hsp[hid];
        return abs(x_ - x[pid]) + abs(y_ - y[pid]);
    };

    vector<int> ord0(n), ord1(n);
    iota(begin(ord0), end(ord0), 0);
    iota(begin(ord1), end(ord1), 0);
    sort(begin(ord0), end(ord0),
         [&](int i, int j) -> bool { return x[i] + y[i] < x[j] + y[j]; });
    sort(begin(ord1), end(ord1),
         [&](int i, int j) -> bool { return x[i] - y[i] < x[j] - y[j]; });
    vector<int> pos0(n), pos1(n);
    for (int i = 0; i < n; ++i) {
        pos0[ord0[i]] = i;
        pos1[ord1[i]] = i;
    }

    bool ans = false;
    array<vector<vector<int>>, 4> dps;
    fill(begin(dps), end(dps),
         vector<vector<int>>(n + 1, vector<int>(t + 1, 0)));
    for (int sp0 = 0; sp0 <= n; ++sp0) {
        for (int i = 0; i < n; ++i) {
            int p = ord1[i];
            // region 0, 1
            copy(begin(dps[0][i]), end(dps[0][i]), begin(dps[0][i + 1]));
            copy(begin(dps[1][i]), end(dps[1][i]), begin(dps[1][i + 1]));
            if (pos0[p] < sp0) {
                // add to region 0
                int d0 = dist(0, p), d1 = dist(1, p);
                for (int j = t; j >= 0; --j) {
                    dps[0][i + 1][j] += d1;
                    if (j >= d0) {
                        chmin(dps[0][i + 1][j], dps[0][i + 1][j - d0]);
                    }
                }
            } else {
                // add to region 1
                int d1 = dist(1, p), d2 = dist(2, p);
                for (int j = t; j >= 0; --j) {
                    dps[1][i + 1][j] += d2;
                    if (j >= d1) {
                        chmin(dps[1][i + 1][j], dps[1][i + 1][j - d1]);
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            int p = ord1[i];
            // region 2, 3
            copy(begin(dps[2][i + 1]), end(dps[2][i + 1]), begin(dps[2][i]));
            copy(begin(dps[3][i + 1]), end(dps[3][i + 1]), begin(dps[3][i]));
            if (pos0[p] < sp0) {
                // add to region 3
                int d3 = dist(3, p), d0 = dist(0, p);
                for (int j = t; j >= 0; --j) {
                    dps[3][i][j] += d0;
                    if (j >= d3) {
                        chmin(dps[3][i][j], dps[3][i][j - d3]);
                    }
                }
            } else {
                // add to region 2
                int d2 = dist(2, p), d3 = dist(3, p);
                for (int j = t; j >= 0; --j) {
                    dps[2][i][j] += d3;
                    if (j >= d2) {
                        chmin(dps[2][i][j], dps[2][i][j - d2]);
                    }
                }
            }
        }
        for (int sp1 = 0; sp1 <= n; ++sp1) {
            for (int i = 0; i <= t; ++i) {
                int cur = i;
                bool ok = true;
                for (int k = 0; k < 4; ++k) {
                    cur = t - dps[k][sp1][cur];
                    if (cur < 0) {
                        ok = false;
                        break;
                    }
                }
                if (ok && cur >= i) {
                    ans = true;
                }
            }
        }
    }
    cout << (ans ? "Yes\n" : "No\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...