結果
問題 | No.2078 魔抜けなパープル |
ユーザー | dyktr_06 |
提出日時 | 2024-09-23 06:48:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 2,537 bytes |
コンパイル時間 | 2,249 ms |
コンパイル使用メモリ | 210,480 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-23 06:48:50 |
合計ジャッジ時間 | 3,166 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
5,248 KB |
testcase_01 | AC | 41 ms
5,376 KB |
testcase_02 | AC | 30 ms
5,376 KB |
testcase_03 | AC | 36 ms
5,376 KB |
testcase_04 | AC | 28 ms
5,376 KB |
testcase_05 | AC | 28 ms
5,376 KB |
testcase_06 | AC | 63 ms
5,376 KB |
testcase_07 | AC | 20 ms
5,376 KB |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/2078" #include <bits/stdc++.h> using namespace std; // ax + by + c = 0 -> y = -b/a x - c/a template <typename T> struct Line{ T a, b, c; Line(T A = 0, T B = 0, T C = 0) : a(A), b(B), c(C) {} // 傾き inline bool operator<(const Line &other) const { return -a * other.b < -other.a * b; } inline bool operator>(const Line &other) const { return -a * other.b > -other.a * b; } inline bool operator<=(const Line &other) const { return -a * other.b <= -other.a * b; } inline bool operator>=(const Line &other) const { return -a * other.b >= -other.a * b; } }; template <typename T> struct ConvexHullTrick{ deque<Line<T>> deq; ConvexHullTrick() : deq(){ } bool check(Line<T> l1, Line<T> l2, Line<T> l3){ T a = ((-l3.c * l2.b) - (-l2.c * l3.b)) * ((-l2.a * l1.b) - (-l1.a * l2.b)); T b = ((-l2.c * l1.b) - (-l1.c * l2.b)) * ((-l3.a * l2.b) - (-l2.a * l3.b)); return a >= b; } // l1(x) < l2(x) bool comp(Line<T> l1, Line<T> l2, T x){ // -(ax + c)/b < -(dx + f)/e return -(l1.a * x + l1.c) * l2.b < -(l2.a * x + l2.c) * l1.b; }; // first/second pair<T, T> f(Line<T> l, T x){ T a = -l.a * x - l.c; T b = l.b; if(b < 0) a *= -1, b *= -1; return make_pair(a, b); }; // y = ax + b void add(T a, T b){ Line<T> p(a, -1, b); while((int) deq.size() >= 2 && check(deq.at((int) deq.size() - 2), deq.at((int) deq.size() - 1), p)){ deq.pop_back(); } deq.push_back(p); } // ax + by + c = 0 void add(T a, T b, T c){ Line<T> p(a, b, c); while((int) deq.size() >= 2 && check(deq.at((int) deq.size() - 2), deq.at((int) deq.size() - 1), p)){ deq.pop_back(); } deq.push_back(p); } pair<T, T> query(T x){ while((int) deq.size() >= 2 && !comp(deq.at(0), deq.at(1), x)){ deq.pop_front(); } return f(deq.at(0), x); } }; int main(){ int t; cin >> t; while(t--){ long long x, a; cin >> x >> a; vector<long long> dp(a + 1, 1LL << 60); dp[0] = 0; ConvexHullTrick<long long> CHT; for(long long i = 0; i <= a; i++){ if(i >= 1){ dp[i] = min(dp[i], CHT.query(i).first + i * i + x); } CHT.add(-2 * i, i * i + dp[i]); } cout << dp[a] << "\n"; } }