結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2020-06-04 16:50:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 1,000 ms |
コード長 | 1,497 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 174,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 00:23:45 |
合計ジャッジ時間 | 3,210 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; int main(){ ll n,d,k; cin >> n >> d >> k; vector<ll> x(n); rep(i,n) cin >> x[i]; deque<ll> dq; dq.push_back(0); for(int i=1;i<d;i++){ if(!dq.empty()){ while(x[dq.back()] < x[i]){ dq.pop_back(); if(dq.size() == 0) break; } } dq.push_back(i); } ll ans = 0; int ansj = -1; int ansk = -1; for(int i=d;i<n;i++){ if(!dq.empty()){ while(x[dq.back()] < x[i]){ dq.pop_back(); if(dq.size() == 0) break; } } dq.push_back(i); if(k*(x[dq.front()] - x[i-d]) > ans){ ans = k*(x[dq.front()] - x[i-d]); ansj = i-d; ansk = dq.front(); } if(dq.front()==i-d) dq.pop_front(); } for(int i=n;i<=n+d-1;i++){ if(k*(x[dq.front()] - x[i-d]) > ans){ ans = k*(x[dq.front()] - x[i-d]); ansj = i-d; ansk = dq.front(); } if(dq.front()==i-d) dq.pop_front(); } if(ans==0){ cout << ans << endl; }else{ cout << ans << endl; cout << ansj << " " << ansk << endl; } return 0; }