結果
問題 | No.2643 Many Range Sums Problems |
ユーザー | Forested |
提出日時 | 2024-02-19 22:34:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,478 bytes |
コンパイル時間 | 2,634 ms |
コンパイル使用メモリ | 214,796 KB |
実行使用メモリ | 10,700 KB |
最終ジャッジ日時 | 2024-02-19 22:34:27 |
合計ジャッジ時間 | 12,137 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
ソースコード
#ifndef LOCAL #define FAST_IO #endif // ============ #include <bits/stdc++.h> #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i) #define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i) #define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__) #define ALL(x) begin(x), end(x) #define LEN(x) (i32)(x.size()) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; using pi = pair<i32, i32>; using pl = pair<i64, i64>; template <typename T> using V = vector<T>; template <typename T> using VV = V<V<T>>; template <typename T> using VVV = V<V<V<T>>>; template <typename T> using VVVV = V<V<V<V<T>>>>; template <typename T> using PQR = priority_queue<T, V<T>, greater<T>>; template <typename T> bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template <typename T> bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } template <typename T> i32 lob(const V<T> &arr, const T &v) { return (i32)(lower_bound(ALL(arr), v) - arr.begin()); } template <typename T> i32 upb(const V<T> &arr, const T &v) { return (i32)(upper_bound(ALL(arr), v) - arr.begin()); } template <typename T> V<i32> argsort(const V<T> &arr) { V<i32> ret(arr.size()); iota(ALL(ret), 0); sort(ALL(ret), [&](i32 i, i32 j) -> bool { if (arr[i] == arr[j]) { return i < j; } else { return arr[i] < arr[j]; } }); return ret; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; void scan(char &x) { cin >> x; } void scan(u32 &x) { cin >> x; } void scan(u64 &x) { cin >> x; } void scan(i32 &x) { cin >> x; } void scan(i64 &x) { cin >> x; } void scan(string &x) { cin >> x; } template <typename T> void scan(V<T> &x) { for (T &ele : x) { scan(ele); } } void read() {} template <typename Head, typename... Tail> void read(Head &head, Tail &...tail) { scan(head); read(tail...); } #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__); #define U32(...) \ u32 __VA_ARGS__; \ read(__VA_ARGS__); #define U64(...) \ u64 __VA_ARGS__; \ read(__VA_ARGS__); #define I32(...) \ i32 __VA_ARGS__; \ read(__VA_ARGS__); #define I64(...) \ i64 __VA_ARGS__; \ read(__VA_ARGS__); #define STR(...) \ string __VA_ARGS__; \ read(__VA_ARGS__); #define VEC(type, name, size) \ V<type> name(size); \ read(name); #define VVEC(type, name, size1, size2) \ VV<type> name(size1, V<type>(size2)); \ read(name); // ============ #ifdef DEBUGF #else #define DBG(...) (void)0 #endif bool is_feasible(i32 n, const V<tuple<i32, i32, i64>> &edges) { V<i64> dist(n, INF64); dist[0] = 0; REP(i, n) { bool upd = false; for (auto [u, v, w] : edges) { if (chmin(dist[v], dist[u] + w)) { upd = true; } } if (upd && i == n - 1) { return false; } } return true; } void solve() { I32(n); I64(k); V<i32> r(n); V<i64> x(n); REP(i, n) { read(r[i], x[i]); } V<tuple<i32, i32, i64>> edges; edges.reserve(2 * (n - 1)); REP(i, n) { edges.emplace_back(i + 1, i, 0); edges.emplace_back(i, i + 1, k); } REP(i, n) { V<tuple<i32, i32, i64>> n_edges = edges; n_edges.reserve(2 * (n - 1)); REP(j, n) { if (j != i) { n_edges.emplace_back(j, r[j], x[j]); n_edges.emplace_back(r[j], j, -x[j]); } } if (is_feasible(n + 1, n_edges)) { cout << "Yes\n"; } else { cout << "No\n"; } } } int main() { i32 t = 1; // cin >> t; while (t--) { solve(); } }