Submission #1170046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170046		anteknne	Two Antennas (JOI19_antennas)	C++20	13 / 100	71 ms	45388 KiB

antennas

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

const int MAXN = 2000;
int h[MAXN];
int a[MAXN];
int b[MAXN];
int t[MAXN][MAXN];
int makssuf[MAXN][MAXN];
int wyn[MAXN][MAXN];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) {
        cin >> h[i] >> a[i] >> b[i];
    }

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (i == j) {
                t[i][j] = -1;
                continue;
            }

            bool ok1 = false, ok2 = false;
            if (((i + a[i]) <= j && j <= (i + b[i])) || ((i - b[i]) <= j && j <= (i - a[i]))) {
                ok1 = true;
            }
            if (((j + a[j]) <= i && i <= (j + b[j])) || ((j - b[j]) <= i && i <= (j - a[j]))) {
                ok2 = true;
            }

            if (ok1 && ok2) {
                t[i][j] = abs(h[i] - h[j]);
            } else {
                t[i][j] = -1;
            }

            //cout << i << " " << j << ": " << t[i][j] << "\n";
        }
    }

    //cout << "===";

    for (int i = 0; i < n; i ++) {
        makssuf[i][i] = t[i][i];
        for (int j = i - 1; j >= 0; j --) {
            makssuf[i][j] = max(makssuf[i][j + 1], t[i][j]);
            //cout << i << " " << j << ":  " << makssuf[i][j] << "\n";
        }
    }

    for (int i = 0; i < n; i ++) {
        wyn[i][i] = -1;
        for (int j = i + 1; j < n; j ++) {
            wyn[i][j] = max(wyn[i][j - 1], makssuf[j][i]);
        }
    }

    int q, l, r;
    cin >> q;
    while (q --) {
        cin >> l >> r;
        l --;
        r --;
        cout << wyn[l][r] << "\n";
    }




    return 0;
}

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