Submission #132026

#	Time	Username	Problem	Language	Result	Execution time	Memory
132026		SirCeness	Two Antennas (JOI19_antennas)	C++14	13 / 100	796 ms	63968 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l%&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n, q;
pair<ll, pair<int, int> > arr[2002];

ll dp[2002][2002];

int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		ll a, b, c;
		cin >> a >> b >> c;
		arr[i] = mp(a, mp(b, c));
	}
	
	for (int i = 0; i < 2002; i++) for (int j = 0; j < 2002; j++) dp[i][j] = -1;
	
	for (int i = 0; i < n; i++){
		for (int j = arr[i].second.first+i; j <= min(n-1, arr[i].second.second+i); j++){
			//cout << bas(i) << bas(j) << endl;
			if (arr[j].second.first <= j-i && j-i <= arr[j].second.second){
				dp[i][j] = max(dp[i][j], abs(arr[i].first - arr[j].first));
			}
		}
	}
	
	for (int k = 2; k < n; k++){
		for (int i = 0; i+k<n; i++){
			int j = i+k;
			//cout << bas(i) << bas(j) << endl;
			dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i][j-1]));
		}
	}
	
	cin >> q;
	for (int i = 0; i < q; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		cout << dp[a][b] << endl;
	}
}

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