oj.uz

Submission #1064865

# Submission time Handle Problem Language Result Execution time Memory
1064865 2024-08-18T18:39:58 Z alexdd Train (APIO24_train) C++17
5 / 100
 1000 ms 17284 KB 
#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;
vector<int> train_ends[100005];

void solve_small(int i)
{
    for(int j:train_ends[trains[i].from])
    {
        if(trains[j].tout <= trains[i].tin)
        {
            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 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);
    for(int i=0;i<M;i++)
        train_ends[trains[i].to].push_back(i);
    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);
        }
        solve_small(i);
    }
    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)

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Correct.
2 Correct 2 ms 2908 KB Correct.
3 Correct 2 ms 2652 KB Correct.
4 Correct 1 ms 2652 KB Correct.
5 Correct 1 ms 2796 KB Correct.
6 Correct 1 ms 2652 KB Correct.
7 Correct 1 ms 2652 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13616 KB Correct.
2 Correct 64 ms 17284 KB Correct.
3 Correct 2 ms 2652 KB Correct.
4 Correct 8 ms 4336 KB Correct.
5 Correct 1 ms 2652 KB Correct.
6 Correct 76 ms 13760 KB Correct.
7 Correct 1 ms 2652 KB Correct.
8 Execution timed out 1091 ms 14244 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13616 KB Correct.
2 Correct 64 ms 17284 KB Correct.
3 Correct 2 ms 2652 KB Correct.
4 Correct 8 ms 4336 KB Correct.
5 Correct 1 ms 2652 KB Correct.
6 Correct 76 ms 13760 KB Correct.
7 Correct 1 ms 2652 KB Correct.
8 Execution timed out 1091 ms 14244 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Correct.
2 Correct 2 ms 2908 KB Correct.
3 Correct 2 ms 2652 KB Correct.
4 Correct 1 ms 2652 KB Correct.
5 Correct 1 ms 2796 KB Correct.
6 Correct 1 ms 2652 KB Correct.
7 Correct 1 ms 2652 KB Correct.
8 Correct 57 ms 13616 KB Correct.
9 Correct 64 ms 17284 KB Correct.
10 Correct 2 ms 2652 KB Correct.
11 Correct 8 ms 4336 KB Correct.
12 Correct 1 ms 2652 KB Correct.
13 Correct 76 ms 13760 KB Correct.
14 Correct 1 ms 2652 KB Correct.
15 Execution timed out 1091 ms 14244 KB Time limit exceeded
16 Halted 0 ms 0 KB -