Provando a risolvere i problemi mostra
e multicore
(dal sito delle territoriali, con codeblocks) ho ottenuto due soluzioni che mi sono sembrate corrette (ed effettivamente sono corrette per molteplici subtask) ma che dopo un certo numero di subtask crashano.
La seguente soluzione di mostra
#include <iostream>
using namespace std;
int main(){
freopen("input_14.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T, N, M;
cin >> T;
for (int t = 0; t < T; t++){
cout << endl;
cin >> N >> M;
int V[N], G[M];
for (int i = 0; i < N; i++){
cin >> V[i];
}
for (int i = 0; i < M; i++){
cin >> G[i];
}
int h, f[N][M], m;
bool l = 0;
for (int i = M-1; i >= 0; i--){
if (V[N-1] < G[i]){
h = i;
l = 1;
break;
}
}
if (l == 0){
h = -1;
}
for (int i = 0; i <= h; i++){
f[N-1][i] = 2;
}
for (int i = h+1; i < M; i++){
f[N-1][i] = 1;
}
for (int i = N-2; i >= 0; i--){
for (int j = 0; j < M; j++){
m = f[i+1][j]+1;
for (int x = j; x < M; x++){
if (G[x] > V[i]){
if (x == M-1){
m = max(m, 1+N-i);
}
else {
m = max(m, f[i+1][x+1]+2);
}
}
}
f[i][j] = m;
}
}
cout << "Case #" << t+1 << ": " << f[0][0];
}
}
funziona per i primi 13 subtask ma crasha per il 14esimo.
La seguente soluzione di multicore
#include <iostream>
using namespace std;
struct obj {
int v, w;
};
int main(){
freopen("input_12.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T;
cin >> T;
for (int t = 0; t < T; t++){
cout << endl;
long long int N, M;
cin >> N >> M;
obj O[N];
for (int i = 0; i < N; i++){
cin >> O[i].v >> O[i].w;
}
int f[M+1][2];
for (int i = 0; i <= M; i++){
if (O[0].w <= i){
f[i][0] = O[0].v;
}
else {
f[i][0] = 0;
}
}
for (int i = 1; i < N; i++){
for (int j = 0; (j < O[i].w)&&(j <= M); j++){
f[j][1] = f[j][0];
}
for (int r = 0; r <= M-O[i].w; r++){
f[r+O[i].w][1] = max(f[r+O[i].w][0], O[i].v + f[r][0]);
}
for (int i = 0; i <= M; i++){
f[i][0] = f[i][1];
}
}
cout << "Case #" << t+1 << ": " << f[M][0];
}
}
funziona per i primi 4 subtask ma crasha per il quinto. Questo crash mi rende particolarmente perplesso in quanto ho usato una soluzione pressoché identica a quella che ho usata per ois_lootboxes
sulla piattaforma di allenamento, dove però ho fatto 100/100.
Non riesco a capire perché questi crash avvengono. Qualcuno me lo saprebbe spiegare?
Grazie in anticipo.