結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー | yoshig0731 |
提出日時 | 2020-05-15 08:41:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,047 bytes |
コンパイル時間 | 712 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-09-17 12:57:11 |
合計ジャッジ時間 | 7,579 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 25 ms
6,944 KB |
testcase_14 | AC | 27 ms
6,944 KB |
testcase_15 | AC | 67 ms
6,944 KB |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | AC | 20 ms
6,944 KB |
testcase_19 | RE | - |
testcase_20 | AC | 56 ms
6,944 KB |
testcase_21 | RE | - |
testcase_22 | AC | 56 ms
6,944 KB |
testcase_23 | RE | - |
testcase_24 | AC | 38 ms
6,944 KB |
testcase_25 | RE | - |
testcase_26 | AC | 18 ms
6,940 KB |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | AC | 60 ms
6,944 KB |
testcase_30 | RE | - |
testcase_31 | AC | 24 ms
6,944 KB |
testcase_32 | AC | 27 ms
6,944 KB |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
ソースコード
#include <algorithm> #include <cstdint> #include <cstring> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, s, t) for (int i = s; i < t; i++) #define ALL(obj) obj.begin(), obj.end() #define fcout cout << fixed << setprecision(10) const int iINF = 1e9; const long long llINF = 1e18; const int MOD = 1e9 + 7; template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template <int MOD> struct ModInt { long long val; constexpr ModInt(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr ModInt operator-() const noexcept { return val ? MOD - val : 0; } constexpr ModInt operator+(const ModInt& r) const noexcept { return ModInt(*this) += r; } constexpr ModInt operator-(const ModInt& r) const noexcept { return ModInt(*this) -= r; } constexpr ModInt operator*(const ModInt& r) const noexcept { return ModInt(*this) *= r; } constexpr ModInt operator/(const ModInt& r) const noexcept { return ModInt(*this) /= r; } constexpr ModInt& operator+=(const ModInt& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr ModInt& operator-=(const ModInt& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr ModInt& operator*=(const ModInt& r) noexcept { return *this; } constexpr ModInt& operator/=(const ModInt& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const ModInt& r) const noexcept { return this->val == r.val; } constexpr bool operator!=(const ModInt& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator<<(ostream& os, const ModInt<MOD>& x) noexcept { return os << x.val; } friend constexpr istream& operator>>(istream& is, ModInt<MOD>& x) noexcept { return is >> x.val; } friend constexpr ModInt<MOD> modpow(const ModInt<MOD>& a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; using mint = ModInt<MOD>; long long modpow(long long x, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; } template <typename T> map<T, int> compress(vector<T> x) { map<T, int> res; sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); for (int i = 0; i < x.size(); i++) { res[x[i]] = i; } return res; } template <typename T> int former(const vector<T>& v, T x) { return upper_bound(v.begin(), v.end(), x) - v.begin() - 1; } template <typename T> int latter(const vector<T>& v, T x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); } template <typename T> using Vec = vector<T>; template <typename T> using VVec = vector<vector<T>>; using LL = long long; LL dp[100010]; int main() { int N; LL K; cin >> N >> K; Vec<LL> T(N), D(N); REP(i, N) cin >> T[i] >> D[i]; LL ans = 0; auto f = [&](LL x) { LL las = -K; REP(i, N) { if (D[i] <= x) continue; if (T[i] - las >= K) { las = T[i]; } else { return false; } } return true; }; LL ng = -1, ok = 1e10; while (abs(ok - ng) > 1) { LL mid = (ok + ng) / 2; if (f(mid)) { ok = mid; } else { ng = mid; } } for (auto x : dp) x = -llINF; dp[0] = 0; int left = 0; REP(i, N) { while(T[left] <= T[i] - K) left++; if (!left || T[left - 1] <= T[i] - K) chmax(dp[i + 1], dp[left] + D[i]); if (D[i] <= ok) chmax(dp[i + 1], dp[i]); else left = i + 1; } cout << ok << endl; cout << accumulate(ALL(D), 0LL) - dp[N] << endl; return 0; }