Submission #111785

#	Time	Username	Problem	Language	Result	Execution time	Memory
111785		mechfrog88	Two Antennas (JOI19_antennas)	C++14	13 / 100	570 ms	525312 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;

struct tower{
	ll h;
	ll a,b;
};

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll n;
	cin >> n;
	vector <tower> arr(n+1);
	vector <vector<ll>> d(n+1,vector<ll>(n+1,-1));
	for (int z=0;z<n;z++){
		tower temp;
		cin >> temp.h >> temp.a >> temp.b;
		arr[z+1] = temp;
	}
	for (int x=1;x<=n;x++){
		ll ans = -1;
		for (int y=x+arr[x].a ; y<=n && y <= x+arr[x].b;y++){
			if ( y <= x + arr[x].b && y >= x + arr[x].a &&
				 x >= y - arr[y].b && x <= y - arr[y].a)
				ans = max(ans,abs(arr[x].h-arr[y].h));
			d[x][y] = ans;
		}
	}
	for (int x=n;x>-1;x--){
		for (int y=n-1;y>-1;y--){
			d[y][x] = max(d[y][x],d[y+1][x]);
		}
	}
	for (int x=0;x<=n;x++){
		for (int y=1;y<=n;y++){
			d[x][y] = max(d[x][y],d[x][y-1]);
		}
	}
	// for (int z=1;z<=n;z++){
	// 	for (int x=1;x<=n;x++){
	// 		cout << d[z][x] << ",";
	// 	}
	// 	cout << endl;
	// }
	ll q;
	cin >> q;
	for (int z=0;z<q;z++){
		ll a,b;
		cin >> a >> b;
		cout << d[a][b] << endl;
	}
	cin >> q;
}

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