結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2021-02-05 04:14:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 1,000 ms |
コード長 | 4,355 bytes |
コンパイル時間 | 2,559 ms |
コンパイル使用メモリ | 136,972 KB |
最終ジャッジ日時 | 2025-01-18 11:40:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}template<typename Monoid>struct SegmentTree{using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;SegmentTree(const F f, const Monoid& M1) : f(f), M1(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 resize(int n){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[k << 1], seg[k << 1 | 1]);}}void update(int k, const Monoid &x){k += sz;seg[k] = x;while(k >>= 1){seg[k] = f(seg[k << 1], seg[k << 1 | 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];}// (type = true) : find_last// (type = false) : find_firsttemplate<typename C>int find_subtree(int a, const C &check, Monoid &M, bool type){while(a < sz){Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]);if(check(nxt)) a = a << 1 | type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template<typename C>int find_first(int a, const C &check){Monoid L = M1;if(a <= 0){if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1){Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template<typename C>int find_last(int b, const C &check){Monoid R = M1;if(b >= sz){if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1){if(b & 1){Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, D, K;cin >> N >> D >> K;vector<vector<int>> pos(1000001);SegmentTree<int> seg(N, [](int a, int b){return max(a, b);}, 0);for(int i = 0; i < N; ++i){int x;cin >> x;pos[x].emplace_back(i);seg.set(i, x);}seg.build();int ans = 0, l = -1, r = -1;for(int i = 0; i < N - 1; ++i){int benefit = seg.query(i, min(N, i + D + 1)) - seg[i];if(benefit > 0){if(chmax(ans, benefit)){l = i;int j = seg[i] + benefit;r = *lower_bound(begin(pos[j]), end(pos[j]), i);}}}cout << (ll)ans * K << endl;if(ans > 0) cout << l << ' ' << r << endl;return 0;}