제출 #1252314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252314		antonn	Bodyguard (JOI21_bodyguard)	C++20	42 / 100	25071 ms	416640 KiB

bodyguard

#pragma GCC optimize ("Ofast, unroll-loops")
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = 2'000'000'000;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<ll, 5>> vips;
    vector<ll> l = {-INF, INF}, c = {-INF, INF}, v1, v2;
    for (int i = 1; i <= n; i++) {
        ll t, a, b, cost;
        cin >> t >> a >> b >> cost;
        ll len = abs(a - b);
        ll e = t - a;
        ll f = t + a;
        ll g = t + len - b;
        ll h = t + len + b;
        l.push_back(e);
        l.push_back(g);
        c.push_back(f);
        c.push_back(h);
        vips.push_back({e, f, g, h, cost / 2});
        if (a < b) {
            v1.push_back(e);
        } else {
            v2.push_back(f);
        }
    }
    sort(l.begin(), l.end());
    sort(c.begin(), c.end());
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    l.resize(unique(l.begin(), l.end()) - l.begin());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
    auto idl = [&](ll x) {
        return lower_bound(l.begin(), l.end(), x) - l.begin();
    };
    auto idc = [&](ll x) {
        return lower_bound(c.begin(), c.end(), x) - c.begin();
    };
    for (int i = 0; i < v1.size(); i++) {
        v1[i] = idl(v1[i]);
    }
    for (int i = 0; i < v2.size(); i++) {
        v2[i] = idc(v2[i]);
    }
    vector<vector<ll>> dp1(l.size(), vector<ll>(c.size()));
    vector<vector<ll>> dp2(l.size(), vector<ll>(c.size()));
    vector<vector<ll>> dp(l.size(), vector<ll>(c.size()));
    for (auto [a, b, c, d, z] : vips) {
        if (a == c) {
            for (int j = idc(b); j < idc(d); j++) {
                assign_max(dp1[idl(a)][j], z);
            }
        } else {
            for (int i = idl(a); i < idl(c); i++) {
                assign_max(dp2[i][idc(b)], z);
            }
        }
    }
    for (int i = l.size() - 2; i >= 0; i--) {
        for (int j = c.size() - 2; j >= 0; j--) {
            assign_max(dp[i][j], dp[i + 1][j] + dp2[i][j] * (l[i + 1] - l[i]));
            assign_max(dp[i][j], dp[i][j + 1] + dp1[i][j] * (c[j + 1] - c[j]));
        }
    }
    for (int i = 0; i < q; i++) {
        ll a, b;
        cin >> a >> b;
        ll h = a - b;
        ll w = a + b;
        ll ans = 0;
        ll ind_h = idl(h);
        ll ind_w = idc(w);
        auto it = lower_bound(v2.begin(), v2.end(), ind_w);
        while (it != v2.end()) {
            assign_max(ans, dp[ind_h][*it] + dp2[ind_h - 1][*it] * (l[ind_h] - h));
            it++;
        }
        it = lower_bound(v1.begin(), v1.end(), ind_h);
        while (it != v1.end()) {
            assign_max(ans, dp[*it][ind_w] + dp1[*it][ind_w - 1] * (c[ind_w] - w));
            it++;
        }
        cout << ans << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bodyguard.cpp:1:44: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize ("Ofast, unroll-loops")
      |                                            ^
bodyguard.cpp:9:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    9 | bool assign_min(T& a, T b) {
      |                          ^
bodyguard.cpp:18:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   18 | bool assign_max(T& a, T b) {
      |                          ^
bodyguard.cpp:28:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   28 | int main() {
      |          ^
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:63:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   63 |     auto idl = [&](ll x) {
      |                        ^
bodyguard.cpp:66:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   66 |     auto idc = [&](ll x) {
      |                        ^

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