Poproszę o pomoc w tym zadaniu, nie mogę znaleźć testów dla których mój kod daje błędną odpowiedź.
Link do zadania: http://pl.spoj.com/problems/HOT/
Kod:
#include <stdio.h>
#include <vector>
using namespace std;
struct hotel{
int price;
int dist;
};
int main() {
int distance, count, lastDist = 0;
scanf("%i%i", &distance, &count);
vector<hotel> hotels;
hotel start;
start.dist = 0;
start.price = 0;
hotels.push_back(start);
while (count--) {
vector<hotel> newHotels;
int dist, price;
scanf("%i%i", &dist, &price);
int deltaDist = dist - lastDist;
for (int i = 0; i < hotels.size(); i++) {
hotel stay, pass;
stay.price = hotels[i].price + price;
stay.dist = 0;
pass.price = hotels[i].price;
pass.dist = hotels[i].dist + deltaDist;
newHotels.push_back(stay);
if(pass.dist < 800)
newHotels.push_back(pass);
}
hotels = newHotels;
lastDist = dist;
}
for (int i = 0; i < hotels.size(); i++) {
if (hotels[i].dist + distance - lastDist > 800) {
hotels[i] = hotels[hotels.size() - 1];
hotels.pop_back();
i--;
}
}
int lowestPrice = hotels[0].price;
for (int i = 1; i < hotels.size(); i++) {
if (hotels[i].price < lowestPrice)
lowestPrice = hotels[i].price;
}
printf("%i", lowestPrice);
}