結果

問題 No.2078 魔抜けなパープル
コンテスト
ユーザー dyktr_06
提出日時 2024-09-23 06:48:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 2,537 bytes
コンパイル時間 2,126 ms
コンパイル使用メモリ 203,452 KB
最終ジャッジ日時 2025-02-24 11:40:12
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
    }
}
0