제출 #997295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997295		saddd	은하철도 (APIO24_train)	C++17	0 / 100	1072 ms	13328 KiB

train

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1000003, pr = 31;
const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 500, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e17 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
//#include "train_apio24.h"

#include <vector>


struct E{
    ll x, y, a, b, c;
    bool operator <(const E &other){
        return(a < other.a);
    }
};

int n, m, w;
vt<E>edge;
vt<pll>food;
vt<int>comp;
bool cmp(int a, int b){
    return(edge[a].b < edge[b].b);
}
ll mn[mxn + 1], t[mxn + 1], dp[mxn + 1];
ll solve(){
    sort(ALL(edge));  sort(ALL(comp), cmp); sort(ALL(food));
    int rp = 0;
    ll ans = inf;
    for(int i = 0; i < n; i++)mn[i] = inf;
    mn[0] = 0; 
    for(int i = 0; i < m; i++){
        while(rp < sz(comp) && edge[comp[rp]].b <= edge[i].a){
            if(dp[comp[rp]] == inf)continue;
            auto [x, y, a, b, c] = edge[comp[rp]];
            int id = lower_bound(ALL(food), mpp(b + 1, 1LL * -1)) - food.begin();
            mn[y] = min(mn[y], dp[comp[rp]] - t[y] * id);
            rp++;
        }
        auto [x, y, a, b, c] = edge[i];
        int id = lower_bound(ALL(food), mpp(a, 1LL * -1)) - food.begin() - 1;
        if(id != -1 && food[id].se >= a)id--;
        if(mn[x] == inf)dp[i] = inf;
        else dp[i] = mn[x] + 1LL * (id + 1) * t[x] + c;
        if(y == n - 1){
            int id = lower_bound(ALL(food), mpp(b + 1, 1LL * -1)) - food.begin();
            ans = min(ans, dp[i] + (w - id) * t[n - 1]);
        }
    }
    if(ans == inf)ans = -1;
    return(ans);
}
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) {
    n = N; m = M; w = W;
    for(int i = 0; i < n; i++)t[i] = T[i];
    for(int i = 0; i < m; i++){
        edge.pb({X[i], Y[i], A[i], B[i], C[i]}); comp.pb(i);
    }
    for(int i = 0; i < w; i++){
        food.pb(mpp(L[i], R[i]));
    }
	return(solve());
}

/*
#include <cassert>
#include <cstdio>

#include <vector>

signed main() {
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N);
  std::vector<int> x(M);
  std::vector<int> y(M);
  std::vector<int> a(M);
  std::vector<int> b(M);
  std::vector<int> c(M);
  std::vector<int> l(W);
  std::vector<int> r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
*/

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