Ciao a tutti, vi chiedo una mano per il problema Tournament Planning. Con la mia soluzione ottengo 85/100 (fallisce solo l’ultimo Testcase).
Ho usato bottom-up dynamic programming, dove la tabella m[DAY][TIME] contiene il massimo denaro che si puo’ avere in un determinato giorno/istante. Scorro la tabella in avanti e aggiorno ogni entry con il massimo tra valore della cella precedente e valore della cella corrente. Per ogni cella che visito faccio una ricerca binaria tra i tornei (array di tuple ordinato per giorno, inizio, fine, buy-in, premio) e, se trovo un torneo a cui posso partecipare, aggiorno la tabella nell’istante corrispondente alla fine del torneo con la nuova somma di denaro ($ attuali - buy-in + premio). Cosi’ facendo, in m[999][999] dovrebbe esserci la massima somma ottenibile.
#include<bits/stdc++.h>
// constraints
#define MAXN 100010
#define MAXT 1010
typedef long long ll;
// input data
int N, M, i, j;
int D, S, E, B, P;
ll m[MAXT][MAXT];
std::tuple<ll, ll, ll, ll, ll> t[MAXN];
int main()
{
scanf("%d %d", &N, &M);
for (i = 0; i < N; i++)
{
scanf("%d %d %d %d %d", &D, &S, &E, &B, &P);
t[i] = std::make_tuple(D, S, E, B, P);
}
std::sort(t, t + N);
m[0][0] = M;
for (i = 0; i < MAXT; i++)
for (j = 0; j < MAXT; j++)
{
if (!j)
{
if (i) m[i][j] = std::max(m[i - 1][MAXT - 1], m[i][j]);
}
else m[i][j] = std::max(m[i][j - 1], m[i][j]);
auto it = std::lower_bound(t, t + N, std::make_tuple(i, j, 0, 0, 0));
while (std::get<0>(*it) == i && std::get<1>(*it) == j && std::get<3>(*it) <= m[i][j])
{
m[i][std::get<2>(*it)] = std::max(m[i][std::get<2>(*it)], m[i][j] + std::get<4>(*it) - std::get<3>(*it));
it++;
}
}
printf("%lld\n", m[MAXT - 1][MAXT - 1]);
return 0;
}
Potete darmi un input che faccia sbagliare il mio programma oppure un suggerimento su cosa ho sbagliato?
Grazie mille,
Marco
