結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2018-09-15 00:22:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 1,000 ms |
コード長 | 1,832 bytes |
コンパイル時間 | 1,762 ms |
コンパイル使用メモリ | 173,528 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-07-20 00:08:41 |
合計ジャッジ時間 | 3,611 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,j,n) for(int i=(j);i<(n);i++)#define erep(i,j,n) for(int i=(j);i<=(n);i++)#define all(i) i.begin(),i.end()#define rall(i) i.rbegin(),i.rend()#define INF 1e9const int mod = 1e9+7;typedef vector<int> vi;typedef vector<string> vs;typedef vector<vi> vvi;typedef pair<int, int> pi;typedef long long i64;template <class Monoid> struct SegmentTree {using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x) {seg[k + sz] = x;}void build() {for(int k = sz - 1; k > 0; --k) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}void update(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1){seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid query(int a, int b) {Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[] (const int &k) const {return seg[k + sz];}};int main() {cin.tie(0);ios::sync_with_stdio(false);int n, d, k;cin >> n >> d >> k;SegmentTree<pi> seg(n, [](pi a, pi b){return max(a, b);}, make_pair(0, 0));vi x(n);rep(i, 0, n) {cin >> x[i];seg.update(i, make_pair(x[i], -i));}i64 ans = 0;int a = -1, b = -1;rep(i, 0, n) {auto v = seg.query(i, min(n, i + d) + 1);if(ans < v.first - x[i]) {ans = v.first - x[i];a = i;b = -v.second;}}cout << ans * k << endl;if(ans > 0) cout << a << " " << b << endl;}