Submission #771087

#	Time	Username	Problem	Language	Result	Execution time	Memory
771087		Dan4Life	Two Antennas (JOI19_antennas)	C++17	13 / 100	354 ms	72408 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)3e3+10;
int n,q,l,r,a[mxN], b[mxN],h[mxN], dp[mxN][mxN];

int compatible(int i, int j){
	if(abs(i-j)>=max(a[i],a[j]) and abs(i-j)<=min(b[i],b[j]))
		return abs(h[i]-h[j]);
	return -1;
}

int main(){
	cin >> n; memset(dp,-1,sizeof(dp));
	for(int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
	for(int i = 1; i <= n; i++)
		for(int j = i+1; j <= n; j++)
			dp[i][j] = compatible(i,j);
	for(int l = 2; l <= n; l++){
		for(int i = 1, j=i+l-1; j <= n; i++,j++){
			dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
			dp[i-1][j] = max(dp[i-1][j],dp[i][j]);
		}
	}
	cin >> q;while(q--) cin>>l>>r,cout<<dp[l][r]<<"\n";
}

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