Submission #1170099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170099		4QT0R	Two Antennas (JOI19_antennas)	C++20	13 / 100	261 ms	589824 KiB

antennas

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

vector<vector<int>> dp;
int n;
vector<int> h;
vector<pair<int,int>> zas;
vector<set<int>> into;

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

	cin >> n;
	h.resize(n);
	zas.resize(n);
	into.resize(n);
	dp.resize(n,vector<int>(n,-1));
	for (int i = 0; i<n; i++){
		cin >> h[i] >> zas[i].first >> zas[i].second;
		for (int j = i+zas[i].first; j<n && j-i<=zas[i].second; j++){
			into[j].insert(i);
		}
	}
	for (int i = 1; i<n; i++){
		for (int j = i-1; j>=0; j--)dp[j][i]=dp[j][i-1];
		for (int j = i-1; j>=0; j--){
			auto it=into[i].find(j);
			if (it!=into[i].end() && (i-j>=zas[i].first) && (i-j<=zas[i].second)){
				dp[j][i]=max(dp[j][i],abs(h[i]-h[j]));
			}
			dp[j][i]=max(dp[j][i],dp[j+1][i]);
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		cout << dp[a][b] << '\n';
	}
}

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