Submission #999592

#	Time	Username	Problem	Language	Result	Execution time	Memory
999592		MarwenElarbi	Two Antennas (JOI19_antennas)	C++17	13 / 100	347 ms	524288 KiB

antennas

#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;
  }
}

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