結果

問題 No.2078 魔抜けなパープル
コンテスト
ユーザー dyktr_06
提出日時 2022-12-09 17:39:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 1,358 bytes
コンパイル時間 1,635 ms
コンパイル使用メモリ 174,048 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 18:46:51
合計ジャッジ時間 2,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/2078"
#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct ConvexHullTrick{
    deque<pair<T, T>> deq;

    ConvexHullTrick(): deq(){
    }

    bool check(pair<T, T> line1, pair<T, T> line2, pair<T, T> line3){
        return (line2.first - line1.first) * (line3.second - line2.second) >= (line2.second - line1.second) * (line3.first - line2.first);
    }

    T f(pair<T, T> line, T x){
        return line.first * x + line.second;
    }

    void add(T a, T b){
        pair<T, T> p = {a, 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);
    }

    T query(T x){
        while((int) deq.size() >= 2 && f(deq.at(0), x) >= f(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) + i * i + x);    
            }
            CHT.add(-2 * i, i * i + dp[i]);
        }
        cout << dp[a] << "\n";
    }
}
0