結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-25 00:32:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 1,000 ms |
コード長 | 1,528 bytes |
コンパイル時間 | 1,735 ms |
コンパイル使用メモリ | 171,008 KB |
実行使用メモリ | 8,784 KB |
最終ジャッジ日時 | 2024-07-19 23:17:16 |
合計ジャッジ時間 | 3,411 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAX_N = 1 << 17;const int def = 1 << 25;const int INF = 1 << 25;typedef pair<ll, int> Node;struct MinSegTreeIdx {int n;Node node[2 * MAX_N - 1];int minIdx[2 * MAX_N - 1];void init(int n_) {n = 1;while(n < n_) n *= 2;for(int i = 0; i < 2 * n - 1; i++) node[i] = make_pair(def, INF);}Node merge(Node l, Node r) {if(l.first <= r.first) return l;return r;}void update(int k, ll a) {k += n - 1;node[k] = make_pair(a, k - (n - 1));minIdx[k] = k - (n - 1);while(k > 0) {k = (k - 1) / 2;node[k] = merge(node[k * 2 + 1], node[k * 2 + 2]);}}Node query(int a, int b) { return query(a, b, 0, 0, n); }Node query(int a, int b, int k, int l, int r) {if(r <= a || b <= l) return make_pair(def, INF);if(a <= l && r <= b) return node[k];Node vl = query(a, b, k * 2 + 1, l, (l + r) / 2);Node vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return merge(vl, vr);}};MinSegTreeIdx st;ll x[100000];int main() {cin.tie(0);ios::sync_with_stdio(false);int N, D;ll K;cin >> N >> D >> K;st.init(N);for(int i = 0; i < N; i++) {cin >> x[i];st.update(i, x[i]);}ll ans = 0, ansj = -1, ansk = -1;for(int i = 0; i < N; i++) {Node res = st.query(max(i - D, 0), i + 1);if((x[i] - res.first) * K > ans) {ans = (x[i] - res.first) * K;ansj = i;ansk = res.second;}}cout << ans << endl;if(ans != 0) {cout << ansk << " " << ansj << endl;}}