結果

問題 No.2078 魔抜けなパープル
ユーザー dyktr_06dyktr_06
提出日時 2022-12-09 17:39:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 48 ms / 2,000 ms
コード長 1,358 bytes
コンパイル時間 1,932 ms
コンパイル使用メモリ 170,880 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-22 19:14:36
合計ジャッジ時間 2,716 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
5,248 KB
testcase_01 AC 35 ms
5,376 KB
testcase_02 AC 23 ms
5,376 KB
testcase_03 AC 30 ms
5,376 KB
testcase_04 AC 21 ms
5,376 KB
testcase_05 AC 23 ms
5,376 KB
testcase_06 AC 48 ms
5,376 KB
testcase_07 AC 16 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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