Scmax-traccia del problema

Chiarimenti
1

è da ieri che sto cercando di capire questo problema ma c è un aspetto che non riesco a comprendere
either Sj < Sj+1 or Sj+1 = CSj
vuol dire che se io ho una nota che soddisfi entrambe le condizioni non la devo accettare ?
tipo
4
1 2 2 2
2 3 4 5
qui stamperebbe 1 o 2 ?
io ho provato con un approccio dp(ancora non ottimizzato),ma mi sbaglia i primi due sub del 2°subtask.

2

Non credo che intendessero exclusive or, almeno la mia sol non lo prende in considerazione :slightly_smiling_face:, sarà un normalissimo bug nel codice.

3

perchè ho provato con una semplice quadratica che poi andrò a sostituire con una N*log N ma non riesco a capire dove sbaglia
e penso sia un problema di mancata comprensione della traccia qui linko il code ->
ho modificato il code rendendolo una vera e propria dp quadratica ma non funziona xd:

#include <bits/stdc++.h>
using namespace std;
int dp[100001];
int main()
{
	int N;
	cin>>N;
	int vet[N],ret[N];
	for(int i=0;i<N;i++){
		cin>>vet[i];
	}
	for(int i=0;i<N;i++){
		cin>>ret[i];
	}
	int sol=-1;
	for(int i=0;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(vet[i]<vet[j] || ret[i]==vet[j]){
				dp[j]=max(dp[j],dp[i]+1);
			}
		}
		sol=max(sol,dp[i]);
	}
	cout<<sol+1;
}
4

ok ho risolto avevo compreso male la traccia xd

5

Ah bene, infatti non capivo molto del codice :sweat_smile: