Submission #895497

#	Time	Username	Problem	Language	Result	Execution time	Memory
895497		kh0i	Two Antennas (JOI19_antennas)	C++17	13 / 100	50 ms	22612 KiB

antennas

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

using ll = long long;

const int N = 2e5 + 3;

int n, q;
int h[N], a[N], b[N], l[N], r[N];

namespace Sub12{
    bool valid_input(){ return n <= 2000; }

    int f[2003][2003];

    int calc(int i, int j){
        int d = abs(j - i);
        if(d < a[i] or d > b[i] or d < a[j] or d > b[j])
            return -1;
        return abs(h[i] - h[j]);
    }

    void solve(){
        for(int i = 1; i <= n; ++i)
            f[i][i] = -1;

        for(int len = 2; len <= n; ++len)
            for(int l = 1, r = len; r <= n; ++l, ++r)
                f[l][r] = max(max(f[l + 1][r], f[l][r - 1]), calc(l, r));

        for(int i = 1; i <= q; ++i)
            cout << f[l[i]][r[i]] << '\n';
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for(int i = 1; i <= q; ++i)
        cin >> l[i] >> r[i];

    if(Sub12::valid_input())
        Sub12::solve();

    return 0;
}

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