| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 997294 | saddd | 은하철도 (APIO24_train) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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));
}
*/