#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct train
{
int from,to;
int tin,tout;
int cost;
};
bool cmp_trains(train x, train y)
{
return x.tin < y.tin;
}
bool cmp_meals(pair<int,int> x, pair<int,int> y)
{
return x.second < y.second;
}
vector<train> trains;
vector<pair<int,int>> meals;
long long dp[100005];
vector<int> meal_cost;
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
std::vector<int> R)
{
meal_cost = T;
for(int i=0;i<M;i++)
{
trains.push_back({X[i],Y[i],A[i],B[i],C[i]});
}
for(int i=0;i<W;i++)
{
meals.push_back({L[i],R[i]});
}
sort(trains.begin(),trains.end(),cmp_trains);
sort(meals.begin(),meals.end(),cmp_meals);
int poz_trains=-1,poz_meals=0;
for(int i=0;i<M;i++)
{
dp[i]=INF;
if(trains[i].from==0)
{
long long cnt=0;
for(auto [x,y]:meals)
if(y < trains[i].tin)
cnt++;
dp[i] = min(dp[i], cnt*meal_cost[trains[i].from] + trains[i].cost);
}
while(poz_trains+1 < M && trains[poz_trains+1].tout <= trains[i].tin)
{
poz_trains++;
}
for(int j=0;j<=poz_trains;j++)
{
if(trains[j].to == trains[i].from)
{
long long cnt=0;
for(auto [x,y]:meals)
if(x > trains[j].tout && y < trains[i].tin)
cnt++;
dp[i] = min(dp[i], dp[j] + cnt*meal_cost[trains[i].from] + trains[i].cost);
}
}
}
long long rez=INF;
for(int i=0;i<M;i++)
{
if(trains[i].to==N-1)
{
long long cnt=0;
for(auto [x,y]:meals)
if(x > trains[i].tout)
cnt++;
rez = min(rez, dp[i] + cnt*meal_cost[N-1]);
}
}
if(rez==INF)
return -1;
else
return rez;
}
/**
dp[i] = costul minim de a parcurge o ruta care incepe la nodul 0, a.i. ultimul tren luat sa fie i (cumparam un meal doar daca e obligatoriu)
*/
Compilation message
train.cpp: In function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:38:23: warning: unused variable 'poz_meals' [-Wunused-variable]
38 | int poz_trains=-1,poz_meals=0;
| ^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct. |
2 |
Correct |
1 ms |
344 KB |
Correct. |
3 |
Correct |
1 ms |
348 KB |
Correct. |
4 |
Incorrect |
2 ms |
348 KB |
Wrong Answer. |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1036 ms |
10444 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1036 ms |
10444 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct. |
2 |
Correct |
1 ms |
344 KB |
Correct. |
3 |
Correct |
1 ms |
348 KB |
Correct. |
4 |
Incorrect |
2 ms |
348 KB |
Wrong Answer. |
5 |
Halted |
0 ms |
0 KB |
- |