Submission #259377

#	Time	Username	Problem	Language	Result	Execution time	Memory
259377		keko37	Two Antennas (JOI19_antennas)	C++14	13 / 100	152 ms	51192 KiB

antennas

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

int n, q;
int h[MAXN], a[MAXN], b[MAXN];
int cost[MAXN][MAXN], dp[MAXN][MAXN], res[MAXN][MAXN];

void precompute () {
    memset(cost, -1, sizeof cost);
    memset(dp, -1, sizeof dp);
    memset(res, -1, sizeof res);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] <= j - i && j - i <= b[i] && a[j] <= j - i && j - i <= b[j]) {
                cost[i][j] = abs(h[i] - h[j]);
            }
            dp[i][j] = max(dp[i][j - 1], cost[i][j]);
        }
    }
    for (int rig = 1; rig <= n; rig++) {
        for (int lef = rig - 1; lef >= 1; lef--) {
            res[lef][rig] = max(res[lef + 1][rig], dp[lef][rig]);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
 	if (n > 2000) return 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }
    precompute();
    cin >> q;
    for (int i = 0; i < q; i++) {
        int lef, rig;
        cin >> lef >> rig;
        cout << res[lef][rig] << '\n';
    }
    return 0;
}

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