結果
問題 | No.1715 Dinner 2 |
ユーザー | Fukucchi |
提出日時 | 2021-10-22 23:38:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,367 bytes |
コンパイル時間 | 2,264 ms |
コンパイル使用メモリ | 188,480 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 06:28:18 |
合計ジャッジ時間 | 3,421 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | WA | - |
testcase_11 | AC | 9 ms
6,940 KB |
testcase_12 | AC | 8 ms
6,944 KB |
testcase_13 | AC | 11 ms
6,940 KB |
testcase_14 | AC | 9 ms
6,940 KB |
testcase_15 | AC | 9 ms
6,940 KB |
testcase_16 | AC | 6 ms
6,940 KB |
testcase_17 | AC | 5 ms
6,940 KB |
testcase_18 | WA | - |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 1 ms
6,944 KB |
testcase_22 | WA | - |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 1 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,944 KB |
testcase_29 | AC | 2 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,944 KB |
testcase_31 | AC | 2 ms
6,944 KB |
testcase_32 | AC | 11 ms
6,940 KB |
testcase_33 | AC | 15 ms
6,944 KB |
testcase_34 | AC | 13 ms
6,940 KB |
testcase_35 | AC | 7 ms
6,944 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | WA | - |
testcase_38 | WA | - |
ソースコード
/* #region header */ #pragma GCC optimize("O3") //コンパイラ最適化用 #ifdef LOCAL #define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示 #endif #define _USE_MATH_DEFINES // #include <atcoder/all> // CodeForcesの場合ファイルごとに入れる #include <bits/stdc++.h> // #include <boost/multiprecision/cpp_dec_float.hpp> // #include <boost/multiprecision/cpp_int.hpp> using namespace std; // using namespace atcoder; typedef long long ll; typedef long long LL; typedef long double ld; typedef long double LD; #define ALL(x) x.begin(), x.end() const long long INF = numeric_limits<long long>::max() / 4; const int MOD = 1e9 + 7; // const int MOD=998244353; //略記 #define FF first #define SS second #define int long long #define stoi stoll #define pii pair<int, int> #define PII pair<int, int> #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(x) (int)((x).size()) #define vb vector<bool> #define VB vector<bool> #define vvb vector<vector<bool>> #define VVB vector<vector<bool>> #define vi vector<int> #define VI vector<int> #define vvi vector<vector<int>> #define VVI vector<vector<int>> // rep macro #define FOA(v, a) for (auto &v : a) #define REPname(a, b, c, d, e, ...) e #define REP(...) REPname(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__) #define REP0(x) for (int i = 0; i < (x); ++i) #define REP1(i, x) for (int i = 0; i < (x); ++i) #define REP2(i, l, r) for (int i = (l); i < (r); ++i) #define REP3(i, l, r, c) for (int i = (l); i < (r); i += (c)) #define RREPname(a, b, c, d, e, ...) e #define RREP(...) RREPname(__VA_ARGS__, RREP3, RREP2, RREP1, RREP0)(__VA_ARGS__) #define RREP0(x) for (int i = (x)-1; i >= 0; --i) #define RREP1(i, x) for (int i = (x)-1; i >= 0; --i) #define RREP2(i, r, l) for (int i = (r)-1; i >= (l); --i) #define RREP3(i, r, l, c) for (int i = (r)-1; i >= (l); i -= (c)) const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // input macro template <class T, class U> std::istream &operator>>(std::istream &is, std::pair<T, U> &p) { is >> p.first >> p.second; return is; } template <class T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &i : v) is >> i; return is; } std::istream &operator>>(std::istream &is, __int128_t &a) { std::string s; is >> s; __int128_t ret = 0; for (int i = 0; i < s.length(); i++) if ('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0'; a = ret * (s[0] == '-' ? -1 : 1); return is; } namespace scanner { void scan(int &a) { std::cin >> a; } // void scan(long long &a) { std::cin >> a; } void scan(std::string &a) { std::cin >> a; } void scan(char &a) { std::cin >> a; } void scan(char a[]) { std::scanf("%s", a); } void scan(double &a) { std::cin >> a; } void scan(long double &a) { std::cin >> a; } template <class T, class U> void scan(std::pair<T, U> &p) { std::cin >> p; } template <class T> void scan(std::vector<T> &a) { std::cin >> a; } void INPUT() {} template <class Head, class... Tail> void INPUT(Head &head, Tail &...tail) { scan(head); INPUT(tail...); } } // namespace scanner #define VEC(type, name, size) \ std::vector<type> name(size); \ scanner::INPUT(name) #define VVEC(type, name, h, w) \ std::vector<std::vector<type>> name(h, std::vector<type>(w)); \ scanner::INPUT(name) #define INT(...) \ int __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define LD(...) \ long double __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) int in() { int x; cin >> x; return x; } // https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed#c%E3%81%A7%E3%81%AE%E5%AE%9F%E8%A3%85 void print() { cout << "\n"; } template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); } template <class T> void print(vector<T> &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << "\n"; } template <class T> void print(set<T> &set) { for (auto &a : set) { cout << a << " "; } cout << "\n"; } template <class T> void print(vector<vector<T>> &df) { for (auto &vec : df) { print(vec); } } void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); } void No() { std::cout << "No\n"; } void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); } void NO() { std::cout << "NO\n"; } // debug macro // https://atcoder.jp/contests/abc202/submissions/22815715 namespace debugger { template <class T> void view(const std::vector<T> &a) { std::cerr << "{ "; for (const auto &v : a) { std::cerr << v << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const std::vector<std::vector<T>> &a) { std::cerr << "{\n"; for (const auto &v : a) { std::cerr << "\t"; view(v); std::cerr << "\n"; } std::cerr << "}"; } template <class T, class U> void view(const std::vector<std::pair<T, U>> &a) { std::cerr << "{\n"; for (const auto &p : a) std::cerr << "\t(" << p.first << ", " << p.second << ")\n"; std::cerr << "}"; } template <class T, class U> void view(const std::map<T, U> &m) { std::cerr << "{\n"; for (const auto &p : m) std::cerr << "\t[" << p.first << "] : " << p.second << "\n"; std::cerr << "}"; } template <class T, class U> void view(const std::pair<T, U> &p) { std::cerr << "(" << p.first << ", " << p.second << ")"; } template <class T> void view(const std::set<T> &s) { std::cerr << "{ "; for (auto &v : s) { view(v); std::cerr << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const T &e) { std::cerr << e; } } // namespace debugger #ifdef LOCAL void debug_out() {} template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { debugger::view(H); std::cerr << ", "; debug_out(T...); } #define debug(...) \ do { \ std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \ debug_out(__VA_ARGS__); \ std::cerr << "\b\b]\n"; \ } while (false) #else #define debug(...) (void(0)) #endif long long power(long long x, long long n) { // O(logn) // https://algo-logic.info/calc-pow/#toc_id_1_2 long long ret = 1; while (n > 0) { if (n & 1) ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける x *= x; n >>= 1; // n を1bit 左にずらす } return ret; } // @brief nCr. O(r log n)。あるいは前処理 O(n), 本処理 O(1)で求められる modint // の bc を検討。 int comb(int n, int r) { // https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/ if (n < r) return 0; // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k long long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; // if our approach is correct p = ans and k =1 return p; } // MOD void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; } template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } // 負数も含む丸め long long ceildiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return (a + b - 1) / b; else return a / b; } long long floordiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return a / b; else return (a - b + 1) / b; } long long floorsqrt(long long x) { assert(x >= 0); long long ok = 0; long long ng = 1; while (ng * ng <= x) ng <<= 1; while (ng - ok > 1) { long long mid = (ng + ok) >> 1; if (mid * mid <= x) ok = mid; else ng = mid; } return ok; } // @brief a^n mod mod long long modpower(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // @brief s が c を含むか template <class T> bool contain(const std::string &s, const T &c) { return s.find(c) != std::string::npos; } __attribute__((constructor)) void faster_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cerr.tie(nullptr); } /* #endregion */ // ACL はオーバーフローに注意!!! int n, d; VI A, B; vector<pii> giv; // idx が条件を満たすかどうか bool isOK(int idx) { REP(ni, n) { REP(nj, n) { if (ni == nj) continue; debug(idx, ni, nj); if (A[ni] < idx) { continue; } // if (B[ni] + A[nj] < idx) { // continue; // } int v = B[ni] + B[nj]; debug(idx, ni, nj, v); int koremade = v * (d / 2) - B[nj]; REP(nk, n) { if (d % 2 == 0 and giv[nk].SS != ni and koremade - giv[nk].FF >= idx) { debug(idx, ni, nj, nk, koremade, -giv[nk].FF); return true; } if (d % 2 == 1 and giv[nk].SS != nj and koremade - giv[nk].FF >= idx) return true; } } } return false; } int bin_search() { // ng, okともに広めにとる // 1 以上の整数なら、ng = 0。-1 でバグったことあり int ng = INF; int ok = -INF; while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (isOK(mid)) ok = mid; else ng = mid; } return ok; } signed main() { cin >> n >> d; VI P(n), Q(n); REP(ni, n) { cin >> P[ni] >> Q[ni]; } A.resize(n, 0); B.resize(n, 0); REP(ni, n) { A[ni] = -P[ni]; } REP(ni, n) { B[ni] = -P[ni] + Q[ni]; } REP(ni, n) { giv.PB(MP(-A[ni], ni)); } sort(ALL(giv)); debug(A); debug(B); print(bin_search()); return 0; }