結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2017-03-16 18:15:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 105 ms / 1,000 ms |
コード長 | 2,679 bytes |
コンパイル時間 | 717 ms |
コンパイル使用メモリ | 76,392 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-07-19 23:43:26 |
合計ジャッジ時間 | 3,131 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
// clang-format off#include <cassert>#include <iostream>#include <vector>#include <algorithm>#include <utility>#include <functional>#include <set>#define FOR(i, a, b) for(int i = (a); i < (b); i++)#define RFOR(i, a, b) for(int i = (b)-1; i >= (a); i--)#define rep(i, n) for(int i = 0; i < (n); i++)#define rep1(i,n) for(int i = 1; i <= (n); i++)#define rrep(i, n) for(int i = (n)-1; i >= 0; i--)#define pb push_back#define mp make_pair#define fst first#define snd second#define show(x) cout << #x << " = " << x << endl#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)#define pii pair<int, int>#define vi vector<int>using namespace std;template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T>& p){return o<<"("<<p.first<<","<<p.second<<")";}template<class T> ostream& operator<<(ostream& o,const vector<T>& vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}typedef long long ll;#define MAX 100000int N, D, K;int x[MAX];pii ben[MAX];std::function<bool(const pii&, const pii&)> comp = [](const pii& a, const pii& b)->bool{if(a.fst < b.fst){return true;} else if(a.fst > b.fst){return false;} else {if(a.snd > b.snd){return true;} else if (a.snd < b.snd){return false;} else {return false;}}};int main(){cin >> N >> D >> K;rep(i, N){cin >> x[i];}// vector<pii> mask(D+1);set<pii, decltype(comp)> mask(comp);for(int i = 0; i <= D; i++){mask.insert(mp(x[i], i));// mask[i] = mp(x[i], i);}// [x[i-D-1],...,x[i-1]], x[i]for(int i = D+1; i < N; i++){// sort(mask.begin(), mask.end(), comp);ben[i-D-1] = mp(mask.rbegin()->fst - x[i-D-1], mask.rbegin()->snd);auto ite = mask.lower_bound(mp(x[i-D-1], i-D-1));mask.erase(ite);// mask.pb(mp(x[i], i));mask.insert(mp(x[i], i));}// [x[j],...,x[N-1]]// [x[N-D-1],...,x[N-1]]for(int j = N-D-1; j < N; j++){// sort(mask.begin(), mask.end(), comp);ben[j] = mp(mask.rbegin()->fst - x[j], mask.rbegin()->snd);auto ite = mask.lower_bound(mp(x[j], j));mask.erase(ite);}int max = 0;int max_i = 0;rep(i, N){if(max < ben[i].fst){max = ben[i].fst;max_i = i;}}if(ben[max_i].fst == 0){cout << 0 << endl;} else {cout << (ll)(ben[max_i].fst) * (ll)(K) << endl;cout << max_i << " " << ben[max_i].snd << endl;}return 0;}