Submission #999592

#TimeUsernameProblemLanguageResultExecution timeMemory
999592MarwenElarbiTwo Antennas (JOI19_antennas)C++17
13 / 100
347 ms524288 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
  int n;
  cin>>n;
  int dp[n][n];
  int tab[n][n];
  int a[n],b[n],h[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)
    {
      dp[i][j]=-1e9;
      tab[i][j]=-1e9;
      if((i+a[i]<=j&&j<=i+b[i])||(i-a[i]>=j&&i-b[i]<=j)){
        if((j+a[j]<=i&&i<=j+b[j])||(j-a[j]>=i&&j-b[j]<=i)){
          tab[i][j]=abs(h[i]-h[j]);
        }
      }
    }
  }
  for (int i = n-1; i >=0 ; --i)
  {
    for (int j = i+1; j < n; ++j)
    {
      dp[i][j]=max(tab[i][j],max(dp[i+1][j],dp[i][j-1]));
    }
  }
  int q;
  cin>>q;
  for (int i = 0; i < q; ++i)
  {
    int x,y;
    cin>>x>>y;
    x--;y--;
    cout <<max(-1,dp[x][y])<<endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...