Submission #1057381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057381		beaconmc	Marathon Race 2 (JOI24_ho_t3)	C++14	62 / 100	1517 ms	63572 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;


ll a,b,t, n, l;

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

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

	
	if (cache[x][y][pos] != -1) return cache[x][y][pos];
	if (x==y){
		return cache[x][y][pos]= (n+1) * abs(arr[x]-b);
	}

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

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


}


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

	cin >> n >> l;

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



	ll q;
	cin >> q;


	FOR(i,0,q){
		cin >> a >> b >> t;

		FOR(i,0,2005) FOR(j,0,2005) FOR(k,0,2) cache[i][j][k]=-1;

		ll ans = dp(0, n-1, 0) + abs(a-arr[0]);
		ans = min(ans, dp(0, n-1, 1) + abs(a-arr[n-1]));


		ans += n;


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


	}





}

Compilation message (stderr)

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

• 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