結果
問題 | No.409 ダイエット |
ユーザー |
![]() |
提出日時 | 2019-08-28 06:00:35 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,355 bytes |
コンパイル時間 | 1,973 ms |
コンパイル使用メモリ | 168,004 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-11-17 16:06:48 |
合計ジャッジ時間 | 6,582 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 WA * 44 |
ソースコード
#include "bits/stdc++.h" #include<unordered_map> #include<unordered_set> #include<string> #include<iomanip> #include<iostream> #include<functional> #include<math.h> #include<assert.h> #include<vector> #include<map> #include<set> #include<queue> #include<string> #pragma warning(disable:4996) using namespace std; using ld=long double; const ld eps=1e-9; #define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl; template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){ os << "( " << v.first << ", " << v.second << ")"; return os; } template<class T> ostream& operator <<(ostream &os, const vector<T> &v){ for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os; } template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){ for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os; } template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){ for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os; } template<class T> ostream& operator <<(ostream &os, const set<T> &v){ int i=0; for(auto it:v){ if(i > 0){os << ' ';} os << it; i++; } return os; } using ll = long long int; int N; ll A,B; ll W; ll solve(pair<ll,ll>p,int day){ ll sa=day-p.second; return (p.first+(sa*(sa-1)/2*B-A*(sa-1))); } int main() { std::ios::sync_with_stdio(false); cin>>N>>A>>B>>W; vector<ll>ds(N+1); for(int i=0;i<N;++i)cin>>ds[i+1]; deque<pair<ll,ll>>que; que.emplace_back(W,0); vector<ll>anss(N+1,1e18); anss[0]=W; for(int i=1;i<=N;++i){ auto p=que.front(); anss[i]=solve(p,i)+ds[i]; while(que.size()>=2){ auto p1=que.front(); que.pop_front(); auto p2=que.front(); que.pop_front(); if(solve(p1,i+1)>=solve(p2,i+1)){ que.push_front(p2); }else{ que.push_front(p2); que.push_front(p1); break; } } que.push_back(make_pair(anss[i],i)); while(que.size()>=2){ auto p1=que.back(); que.pop_back(); auto p2=que.back(); que.pop_back(); if(solve(p1,i+1)<=solve(p2,i+1)){ que.push_back(p1); }else{ que.push_back(p2); que.push_back(p1); break; } } } //WHATS(anss); ll answer=1e18; for(int i=0;i<=N;++i){ ll nanswer=anss[i]-(N-i)*A+(N-i)*(N-i+1)/2*B; answer=min(answer,nanswer); } cout<<answer<<endl; return 0; }