제출 #1308481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308481		vako_p	Two Antennas (JOI19_antennas)	C++20	13 / 100	168 ms	55664 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,q,a[mxN],b[mxN],h[mxN],dp[2005][2005];

bool check(ll i, ll j){
  return (j <= i + b[i] and j >= i + a[i] and i >= j - b[j] and i <= j - a[j]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
  for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dp[i][j] = -1;
  for(int i = 1; i <= n; i++){
    for(int j = i - 1; j >= 1; j--){
      dp[j][i] = max(dp[j][i - 1], dp[j + 1][i]);
      if(check(j, i)) dp[j][i] = max(dp[j][i], abs(h[i] - h[j]));
    }
  }
  // for(int i = 1; i <= n; i++){
  //   if(i + a[i] <= n) v[i + a[i]].pb(i);
  //   if(i + b[i] + 1 <= n) v1[i + b[i] + 1].pb(i);
  // }
  // segtree s,s1;
  // s.init();
  // s1.init();
  // for(int i = 1; i <= n; i++){
  //   for(auto it : v1){
  //
  //   }
  // }
  cin >> q;
  while(q--){
    ll l,r;
    cin >> l >> r;
    cout << dp[l][r] << '\n';
  }
}

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