Submission #1200624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200624		anmattroi	Train (APIO24_train)	C++17	5 / 100	1095 ms	6984 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
#define int64_t long long
using namespace std;
using ii = pair<int, int>;
using il = pair<int, int64_t>;
using li = pair<int64_t, int>;

int n, m, w, t[maxn];
struct edge {
    int x, y, a, b, c;

    bool operator < (const edge &other) const {
        return a < other.a;
    }
} edges[maxn];

ii meals[maxn];
int64_t dp[maxn];

int64_t mainProgram() {
    sort(edges + 1, edges + m + 1);
    for (int i = 1; i <= m; i++) dp[i] = LLONG_MAX/2;

    for (int i = 1; i <= m; i++) {
        if (edges[i].x == 1) {
            int cnt = 0;
            for (int j = 1; j <= w; j++) if (meals[j].se < edges[i].a) ++cnt;
            dp[i] = edges[i].c + 1LL * t[edges[i].x] * cnt;
        }
        for (int j = i-1; j >= 1; j--)
        if (edges[j].y == edges[i].x && edges[j].b <= edges[i].a) {
            int cnt = 0;
            for (int k = 1; k <= w; k++) cnt += (edges[j].b < meals[k].fi && meals[k].se < edges[i].a);
            dp[i] = min(dp[i], dp[j] + 1LL * t[edges[i].x] * cnt + edges[i].c);
        }
    }
    int64_t ans = LLONG_MAX;
    for (int i = 1; i <= m; i++)
    if (edges[i].y == n) {
        int cnt = 0;
        for (int j = 1; j <= w; j++) if (meals[j].fi > edges[i].b) ++cnt;
        ans = min(ans, dp[i] + 1LL * t[edges[i].y] * cnt);
    }
    return ans >= LLONG_MAX/2 ? -1 : ans;
}

long long solve(int N, int M, int W, vector<int> T,
                vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C,
                vector<int> L, vector<int> R) {
    n = N; m = M; w = W;
    for (int i = 1; i <= n; i++) t[i] = T[i-1];
    for (int i = 1; i <= m; i++) edges[i] = edge{X[i-1]+1, Y[i-1]+1, A[i-1], B[i-1], C[i-1]};
    for (int i = 1; i <= w; i++) meals[i] = ii{L[i-1], R[i-1]};

	return mainProgram();
}

/*
3 3 1
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19

40
*/
/*
3 5 6
30 38 33
0 2 12 16 38
1 0 48 50 6
0 1 26 28 23
0 2 6 7 94
1 2 49 54 50
32 36
14 14
42 45
37 40
2 5
4 5

197
*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60