Submission #868930

#	Time	Username	Problem	Language	Result	Execution time	Memory
868930		rockstar	Two Antennas (JOI19_antennas)	C++17	13 / 100	250 ms	524288 KiB

antennas

// #pragma GCC optimize("O3,unroll-loops,inline,no-stack-protector")
// #pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,fma,bmi2,abm,popcnt,mmx,tune=native")

#include <bits/stdc++.h>

using namespace std;

#define trace(x) cerr << #x << ": " << (x) << endl;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;

#define int ll

constexpr int INF = numeric_limits<int>::max() / 2;

struct node {
    int h, a, b;
};

void solve() {
    int n;
    cin >> n;
    vector<node> v(n);
    for (auto& i : v)
        cin >> i.h >> i.a >> i.b;
    vector<vector<int>> pref(n, vector<int>(n, -1));
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (v[i].a + i <= j && v[i].b + i >= j && j - v[j].a >= i && j - v[j].b <= i)
                pref[n - i - 1][j] = abs(v[i].h - v[j].h);
    for (int i = 1; i < n; ++i)
        pref[i][0] = max(pref[i][0], pref[i - 1][0]), pref[0][i] = max(pref[0][i], pref[0][i - 1]);
    for (int i = 1; i < n; ++i)
        for (int j = 1; j < n; ++j)
            pref[i][j] = max(pref[i][j], max(pref[i - 1][j], pref[i][j - 1]));
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << pref[n - l - 1][r] << '\n';
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
#ifdef LOCAL
    cerr << '\n' << "time = " << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
#endif
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65