結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:42:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 1,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 1,731 ms |
コンパイル使用メモリ | 169,460 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2024-07-19 22:53:50 |
合計ジャッジ時間 | 3,857 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)#define def -INT_MAX/2template<class V, int NV> class SegTree { // by kmjppublic:V comp(V l, V r) { return max(l, r); };vector<V> val;SegTree() { val = vector<V>(NV * 2, def); }V getval(int l, int r) { //[l,r]l += NV; r += NV + 1;V ret = def;while (l < r) {if (l & 1) ret = comp(ret, val[l++]);if (r & 1) ret = comp(ret, val[--r]);l /= 2; r /= 2;}return ret;}void update(int i, V v) {i += NV;val[i] = v;while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);}};//-----------------------------------------------------------------int N, D, K;int X[101010];SegTree<int, 1 << 20> st;//-----------------------------------------------------------------int main() {cin >> N >> D >> K;rep(i, 0, N) cin >> X[i];rep(i, 0, N) st.update(i, X[i]);int L = -1, C = 0;rep(i, 0, N - 1) {int a = X[i];int b = st.getval(i + 1, i + D);int d = b - a;if (C < d) {C = d;L = i;}}if (L < 0) {printf("0\n");return 0;}rep(i, L, N) {if (X[i] == X[L] + C) {printf("%lld\n", 1LL * C * K);printf("%d %d\n", L, i);return 0;}}}