Ho svolto l’es maturità e ogni test case è corretto tranne l’ultimo della seconda subtask, i anche quando n==3 stampo la difficoltà max.
ho il dubbio che l’output del test case sia sbagliato.
Posta il codice, altrimenti è difficile aiutarti.
#include <iostream>
using namespace std;
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int N,dummy,i=0,j=0,max;
cin>>N;
int sqzP[1000], sqzS[1000];
for (int k=0;k<N;k++){
cin>>dummy;
if (N!=3){
if (k!=1 and k!=N-1){
sqzP[i]=dummy;
i++;
}
if (k!=0 and k!=2){
sqzS[j]=dummy;
j++;
}
}else if (N==3){
if (dummy>max){
max=dummy;
}
}
}
if (N==3){
cout<<max;
return 0;
}
i--;
int app=i-3, pos=i-2; //sqzP
sqzP[i+1]=0;
sqzP[i+2]=0;
// starto dagli ultimi due elementi
while (1){
if (app<=0 and pos<=0){
if (sqzP[1]>sqzP[2]){
sqzP[0]=sqzP[0]+sqzP[1];
break;
}else{
sqzP[0]=sqzP[0]+sqzP[2];
break;
}
}
if (sqzP[app+2]>sqzP[app+3] and app>0){
sqzP[app]=sqzP[app]+sqzP[app+2];
app=app-2;
}else if (app>0){
sqzP[app]=sqzP[app]+sqzP[app+3];
app=app-2;
}
if (sqzP[pos+2]>sqzP[pos+3] and pos>0){
sqzP[pos]=sqzP[pos]+sqzP[pos+2];
pos=pos-2;
}else if (pos>0){
sqzP[pos]=sqzP[pos]+sqzP[pos+3];
pos=pos-2;
}
}
j--;
app=j-3,pos=j-2;
sqzS[j+1]=0;
sqzS[j+2]=0;
while (1){
if (app<=0 and pos<=0){
if (sqzS[1]>sqzS[2]){
sqzS[0]=sqzS[0]+sqzS[1];
break;
}else{
sqzS[0]=sqzS[0]+sqzS[2];
break;
}
}
if (sqzS[app+2]>sqzS[app+3] and app>0){
sqzS[app]=sqzS[app]+sqzS[app+2];
app=app-2;
}else if (app>0){
sqzS[app]=sqzS[app]+sqzS[app+3];
app=app-2;
}
if (sqzS[pos+2]>sqzS[pos+3] and pos>0){
sqzS[pos]=sqzS[pos]+sqzS[pos+2];
pos=pos-2;
}else if (pos>0){
sqzS[pos]=sqzS[pos]+sqzS[pos+3];
pos=pos-2;
}
}
if (sqzP[0]>sqzS[0]){
cout<<sqzP[0];
}else{
cout<<sqzS[0];
}
return 0;
}
Verifica con questo esempio:
5
1 2 3 4 5
grazie mille ho trovato l’errore
la risposta in questo caso non dovrebbe essere otto?
si infatti me ne sono accorto dopo, ora faccio 100/100 in O(N).
Non so come ti sia venuto in mente un input tanto semplice, quanto geniale per il problema,
ma grazie mille
#include <iostream>
#include <vector>
using namespace std;
vector<long long> diffic;
vector<long long> greedy;
vector<long long> solution;
long long K;
long long N;
long long elaboro(vector<long long> a, long long index){
long long sum = 0;
//cout << "indice iniziale " << index << endl;
/* for(int i = 0; i < N + K; i++){
cout << a[i] << " ";
} */
//cout << endl;
for(long long i = index; i < index + K; i++){
if(a[i] == -1){
continue;
} else {
a[i - 1] = -1;
a[i + 1] = -1;
/*for(int i = 0; i < N + K; i++){
cout << a[i] << " ";
} */
//cout << endl;
sum += a[i];
}
}
//cout << sum << endl;
return sum;
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> N;
diffic.resize(N);
for(int i = 0; i < N; i++){
cin >> diffic[i];
}
solution.resize(N);
K = N - 1;
greedy.resize(K + N);
for(int i = 0; i < N; i++){
greedy[i] = diffic[i];
greedy[i + K + 1] = diffic[i];
}
/*for(int i = 0; i < greedy.size(); i++){
cout << greedy[i] << " " << endl;
}*/
int max = 0;
if(N == 3){
for(int i = 0; i < N; i++){
max = (diffic[i] > max) ? diffic[i] : max;
}
cout << max;
return 0;
}
for(long long i = 1; i < N + 1; i++){
solution[i - 1] = elaboro(greedy, i);
}
for(int a = 0; a < solution.size(); a++){
max = (solution[a] > max) ? solution[a] : max;
}
cout << max;
}
io non riesco a capire l’errore del mio codice(non supera il time limit)
Compilando in locale, il tuo codice genera un eccesso di memoria, forse questo è la causa del superamento del tempo limite.
Per risolvere questo inconveniente usa variabili int al posto di long long: in questo esercizio sono sufficienti.
sisi, ho provato a mettere int, ma il mio programma fa soltanto 10/100
Non capisco che testcase possa sbagliare
allego il codice da me sottoposto che prende 10/100
#include <iostream>
#include <vector>
using namespace std;
vector<int> diffic;
vector<int> greedy;
vector<int> solution;
long long K;
long long N;
long long elaboro(vector<int> a, int index){
long long sum = 0;
//cout << "indice iniziale " << index << endl;
/* for(int i = 0; i < N + K; i++){
cout << a[i] << " ";
} */
//cout << endl;
for(long long i = index; i < index + K; i++){
if(a[i] == -1){
continue;
} else {
a[i - 1] = -1;
a[i + 1] = -1;
/*for(int i = 0; i < N + K; i++){
cout << a[i] << " ";
} */
//cout << endl;
sum += a[i];
}
}
//cout << sum << endl;
return sum;
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> N;
diffic.resize(N);
for(int i = 0; i < N; i++){
cin >> diffic[i];
}
solution.resize(N);
K = N - 1;
greedy.resize(K + N);
for(int i = 0; i < N; i++){
greedy[i] = diffic[i];
greedy[i + K + 1] = diffic[i];
}
/*for(int i = 0; i < greedy.size(); i++){
cout << greedy[i] << " " << endl;
}*/
int max = 0;
if(N == 3){
for(int i = 0; i < N; i++){
max = (diffic[i] > max) ? diffic[i] : max;
}
cout << max;
return 0;
}
for(int i = 1; i < N + 1; i++){
solution[i - 1] = elaboro(greedy, i);
}
for(int a = 0; a < solution.size(); a++){
max = (solution[a] > max) ? solution[a] : max;
}
cout << max;
}
usi la tecnica greedy?
Ho controllato il codice e non può funzionare correttamente perché prendi in considerazione solamente gli esami a passo alterno e anche se si considerano tutte le possibilità di una disposizione in cerchio degli esaminatori non sempre si ottiene il risultato corretto.
Con questo input:
8
1 2 9 4 9 5 6 9
il codice fornisce come risultato: 25 = 1 + 9 + 9 + 6, ma si può fare meglio prendendo 9 + 9 + 9 = 27 rispettando sempre le condizioni del problema.
sisi, grazie ho appena implementato il nuovo codice