Submission #1177894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177894		trashaccount	Train (APIO24_train)	C++20	5 / 100	36 ms	12736 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector <int>

const int NM = 1000;
const ll inf = 1e18;

namespace subtask1{
    int N, M, W, f[NM+5][NM+5];
    vi T, X, Y, A, B, C, L, R, od;
    ll d[NM+5];

    int calc(int x, int y){
        if (x > y) return 0;
        return f[x][y];
    }
    ll solve(int _N, int _M, int _W, vi _T, vi _X, vi _Y, vi _A, vi _B, vi _C, vi _L, vi _R){
        N = _N, M = _M, W = _W;
        T = _T, X = _X, Y = _Y, A = _A, B = _B, C = _C, L = _L, R = _R;

        od.clear();
        for (int i = 0; i < M; i++) od.push_back(i);
        sort(od.begin(), od.end(), [&](int i, int j){
            return B[i] < B[j];
        });

        memset(f, 0, sizeof(f));
        for (int i = 0; i < W; i++) f[L[i]][R[i]]++;
        
        for (int i = NM; i >= 0; i--)
            for (int j = i+1; j <= NM; j++)
                f[i][j] += f[i+1][j]+f[i][j-1]-f[i+1][j-1];

        for (int t1 = 0; t1 < M; t1++){
            int i = od[t1];
            if (X[i] == 0) d[i] = 1LL*calc(0, A[i]-1)*T[X[i]]+C[i];
            else d[i] = +inf;
            for (int t2 = 0; t2 < t1; t2++){
                int j = od[t2];
                if (Y[j] != X[i]) continue;
                if (B[j] > A[i]) continue;
                d[i] = min(d[i], d[j]+1LL*calc(B[j]+1, A[i]-1)*T[X[i]]+C[i]);
            }
        }
        ll ans = +inf;
        for (int t = 0; t < M; t++){
            if (Y[t] != N-1) continue;
            ans = min(ans, d[t]+1LL*calc(B[t]+1, NM)*T[N-1]);
        }
        if (ans == +inf) return -1;
        return ans;
    }
}

ll solve(int N, int M, int W, vi T, vi X, vi Y, vi A, vi B, vi C, vi L, vi R){
    return subtask1::solve(N, M, W, T, X, Y, A, B, C, L, R);
}

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