結果

問題 No.409 ダイエット
ユーザー uenoku
提出日時 2017-02-15 11:38:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,679 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 103,448 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-12-29 22:53:57
合計ジャッジ時間 12,792 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 71 WA * 20 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long long int lli;
int main()
{
    lli a, b, n, w;
    cin >> n >> a >> b >> w;
    lli d[314514];
    rep(i, n) cin >> d[i];
    priority_queue<pair<lli, lli>, vector<pair<lli, lli>>, greater<pair<lli, lli>>> que;
    que.push(make_pair(0, d[0]));
    que.push(make_pair(1, b - a));
    for (int i = 1; i < n; i++) {
        set<int> s;
        map<lli, lli> mi;
        set<int> memo;
        while (!que.empty()) {
            auto j = que.top();
            que.pop();
            lli gain = j.second;
            int dep = j.first;
            //cout << "depth : " << dep << ' ' << gain << endl;
            s.insert(gain);
            auto itr = s.find(gain);

            if (itr != s.begin()) {
                continue;
            }
            if (memo.find(dep) != memo.end()) {
                mi[dep] = min(mi[dep], gain);
            } else {
                mi[dep] = gain;
                memo.insert(dep);
            }
        }
        for (auto j : mi) {
            que.push(make_pair(j.first + 1, j.second + (j.first + 1) * b - a));
            que.push(make_pair(0, j.second + d[i]));
        }
    }
    lli ans = 1e15;
    while (!que.empty()) {
        auto j = que.top();
        que.pop();
        ans = min(ans, j.second);
        int dep = j.first;
        lli gain = j.second;


        //cout << "depth : " << dep << ' ' << gain << endl;
    }
    cout << ans + w << endl;
}
0