Submission #1057426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057426		beaconmc	Marathon Race 2 (JOI24_ho_t3)	C++14	62 / 100	1519 ms	157752 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

const ll maxn = 500005;
const ll INF = 100000000000000000;
ll tree[maxn*4];
ll lazy[maxn*4];

ll calc(ll k){
	return tree[k] + lazy[k];
}

void push(ll k){
	lazy[k*2] += lazy[k];
	lazy[k*2+1] += lazy[k];
	tree[k] += lazy[k];
	lazy[k] = 0;
}
void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y=maxn-1){
	if (b<x || a>y) return;
	if (a<=x && y<=b){
		lazy[k] += val;
		return;
	}

	ll mid = (x+y)/2;
	update(a,b,val,k*2,x,mid);
	update(a,b,val,k*2+1,mid+1,y);

	tree[k] = max(calc(k*2), calc(k*2+1));
}

ll query(ll a, ll b, ll k=1, ll x = 0, ll y =maxn-1){
	if (b<x || a>y) return 0;
	if (a<=x && y<=b){
		return calc(k);
	}
	ll mid = (x+y)/2;

	return max(query(a, b, k*2, x, mid), query(a,b,k*2+1, mid+1, y));
}

ll a,b,t, n, l;

ll arr[2005];
ll cache[2005][2005][2][2];

ll dp(ll x, ll y, ll pos, ll req){



	
	if (cache[x][y][pos][req] != -1) return cache[x][y][pos][req];
	if (x==0 && y==n-1){
		if (pos==req) return 0;
		else return 100000000000000000;
	}


	if (pos == 0){
		ll idk=INF, idk2 = INF;
		if (y<(n-1))idk = dp(x,y+1,1,req) + abs(arr[x]-arr[y+1])*(n-(y-x));

		if (x>0) idk2 = dp(x-1,y,0,req) + abs(arr[x]-arr[x-1])*(n-(y-x));

		return cache[x][y][pos][req]=min(idk, idk2);
	}
 
	else if (pos == 1){
		ll idk=INF, idk2 = INF;
		if(x>0) idk = dp(x-1,y,0,req) + abs(arr[y]-arr[x-1])*(n-(y-x));
		if (y<(n-1)) idk2 = dp(x, y+1, 1,req) + abs(arr[y]-arr[y+1]) * (n-(y-x));
		return cache[x][y][pos][req]=min(idk, idk2);
	}


}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	FOR(i,0,maxn*4) tree[i] = 0, lazy[i] = 0;
	FOR(i,0,2005) FOR(j,0,2005) FOR(k,0,2)FOR(l,0,2) cache[i][j][k][l]=-1;


	cin >> n >> l;

	FOR(i,0,n) cin >> arr[i];
	sort(arr, arr+n);






	ll q;
	cin >> q;

	FOR(i,0,q){
		FOR(i,0,2005) FOR(j,0,2005) FOR(k,0,2)FOR(l,0,2) cache[i][j][k][l]=-1;
		cin >> a >> b >> t;
		ll ans = INF;

		FOR(j,0,n){
			ans = min(ans, dp(j,j,0,0)+abs(arr[0]-a) + (n+1)*abs(b-arr[j]));
			ans = min(ans, dp(j,j,0,1)+abs(arr[n-1]-a) + (n+1)*abs(b-arr[j]));
		}

		if (ans+n <= t) cout << "Yes" << "\n";
		else cout << "No" << "\n";






	}
	// vector<vector<ll>> queries;

	// FOR(i,0,q){
	// 	cin >> a >> b >> t;
	// 	queries.push_back({b, a, t, i});
	// }
	// sort(queries.begin(), queries.end());

	// for (auto&i : queries){

	// }






}

Compilation message (stderr)

Main.cpp: In function 'll dp(ll, ll, ll, ll)':
Main.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19