結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2020-09-13 18:48:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 1,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 1,031 ms |
コンパイル使用メモリ | 97,604 KB |
最終ジャッジ日時 | 2025-01-14 14:32:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <deque>#include <functional>template <class T>struct SlidingWindow {using Cmp = std::function<bool(T, T)>;std::deque<std::pair<T, int>> window;Cmp cmp;int l, r;explicit SlidingWindow(Cmp cmp): window(), cmp(cmp), l(0), r(0) {}void push(T val) {while (!window.empty() && cmp(val, window.back().first)) {window.pop_back();}window.emplace_back(val, r++);}std::pair<T, int> get() {return window.front();}void pop() {if (window.front().second == l++) {window.pop_front();}}};using lint = long long;void solve() {int n, d, k;std::cin >> n >> d >> k;SlidingWindow<int> sw([](auto a, auto b) { return a < b; });int max = 0, l = -1, r = -1;for (int i = 0; i < n; ++i) {int x;std::cin >> x;sw.push(x);auto [y, j] = sw.get();if (x - y > max) {max = x - y;l = j, r = i;}if (i >= d) sw.pop();}if (max <= 0) {std::cout << "0\n";} else {std::cout << lint(max) * k << "\n"<< l << " " << r << "\n";}}int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);solve();return 0;}