# Codeforces: Mr. Kitayuta, the Treasure Hunter

**URL:** <https://forum.olinfo.it/t/codeforces-mr-kitayuta-the-treasure-hunter/9026>\
**Category:** Altre gare\
**Created:** [3 Ottobre 2024, 8:39am UTC](https://forum.olinfo.it/t/codeforces-mr-kitayuta-the-treasure-hunter/9026 "2024-10-03T08:39:55Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [3 Ottobre 2024, 8:39am UTC](https://forum.olinfo.it/t/codeforces-mr-kitayuta-the-treasure-hunter/9026/1 "2024-10-03T08:39:56Z")

</div>

Ho “risolto” questo [problema](https://codeforces.com/contest/505/problem/C) su codeforces, almeno in teoria.  
Il problema consiste nel trovare il maggior numero di gemme che possono essere raccolte lungo un rettilineo lungo 30001 isole (da 0 a 30000), inizialmente si parte dall’isola 0 e si fa un salto lungo d (1 \<= d \<= 30000) ogni salto successivo a questo può essere lungo uguale a quello precedente, o avere la stessa lunghezza ± 1.  
Spiegazione:

si utilizza una dp i,j dove i indica la posizione sul rettilineo e j indica il salto con cui sei arrivato a questa posizione (i salti possibili sono solo [d-246, d+246] )

Il problema è che sul quarto testcase ricevo un output sbagliato, ovviamente ho guardato la soluzione e ho anche rannato il mio codice insieme a quello della soluzione su migliaia di testcases generati randomicamente e sempre hanno generato gli stessi risultati. Ho paura che la colpa sia della differenza tra i compilatori utilizzati sulla piattaforma e sul mio pc.

[codice della soluzione](https://ideone.com/GLXkVj)

mio codice:

```auto
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
 
int nxt() {int x;cin >> x;return x;}
 
void solve();
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
	// cin>>t;
	rep(i,t){
		solve();
	}
}

void solve(){
	int n,d;
	cin>>n>>d;
	// vector<int> arr(30001); //you can use both this commented code or the one below it (one is push dp the other pull dp) in both cases the output to testcase 4 is 19078 instead of 22500
	// rep(i,n)arr[nxt()]++;
	// int mini = d,maxi = d;
	// int cur = d;
	// while(cur <= 30000 && mini > 1)cur += --mini;
	// cur = d;
	// while(cur <= 30000)cur += ++maxi;
	// vector<vector<int>> dp(30001,vector<int>(maxi-mini+1,-1));
	// dp[d][d-mini] = arr[d];
	// rep(i,30001){
	// rep(j,maxi-mini+1)if(dp[i][j] != -1 && i + j + mini -1 <=30000){
	// rep(z,3)if(i + j + mini -1 + z <= 30000 && j -1 + z >= 0)dp[i+j+mini-1+z][j-1+z] = max(dp[i+j+mini-1+z][j-1+z], dp[i][j] + arr[i+j+mini-1+z]);
	// }
	// }
	// int ans = 0;
	// for(auto x : dp[30000])ans = max(ans,x);
	// cout<<ans<<endl;
	vector<int> arr(30001);
	rep(i,n)arr[nxt()]++;
	int average = 250;
	vector<vector<int>> dp(30001,vector<int>(average*2,-1));
	dp[d][average] = arr[d];
	rep(i,30001)for(int j =1; j<2*average;j++)if(d - average + j > 0 && i - (d - average + j) >= 0){
		int jumpf = d - average + j;
		if(i-jumpf>=0)rep(z,3){
			int jump = jumpf - 1 + z;
			if(jump > 0 && jump - d + average < 500 && dp[i-jumpf][jump-d+average] != -1)dp[i][j] = max(dp[i][j], dp[i - jumpf][jump - d + average] + arr[i]);
		}
	}
	int ans = 0;
	for(auto x : dp[30000])ans=max(ans,x);
	cout<<ans<<endl;
}

```

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [3 Ottobre 2024, 3:22pm UTC](https://forum.olinfo.it/t/codeforces-mr-kitayuta-the-treasure-hunter/9026/2 "2024-10-03T15:22:08Z")

</div>

Soluzione: non bisogna guardare il risultato di quando arrivi all’isola 30001 ma all’isola di dove ti fermi (il risultato è il massimo in tutta la dp, non in dp[30000])