結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:33:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 1,000 ms |
コード長 | 1,734 bytes |
コンパイル時間 | 1,585 ms |
コンパイル使用メモリ | 171,212 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 22:52:55 |
合計ジャッジ時間 | 2,683 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }template<typename Val, typename Cmp = less<Val> >struct MonotonicQueue {vector<pair<Val, int>> q;int head, tail;Cmp cmp;MonotonicQueue(Cmp cmp = Cmp()) : cmp(cmp) {}void init(int n) {q.resize(n);clear();}bool empty() const { return head == tail; }void clear() {head = tail = 0;}void enque(int i, Val x) {while (head < tail && cmp(x, q[tail - 1].first))-- tail;q[tail ++] = make_pair(x, i);}void deque(int i) {if (head < tail && q[head].second == i)++ head;}Val get() const {return q[head].first;}pair<Val,int> getPair() const {return q[head];}};int main() {int N; int D; int K;while (~scanf("%d%d%d", &N, &D, &K)) {pair<ll, pii> ans(0, make_pair(0, 0));MonotonicQueue<int, less<int>> mq;mq.init(N);rep(i, N) {int x;scanf("%d", &x);if (i > 0) {auto p = mq.getPair();amin(ans, make_pair((ll)p.first - x, make_pair(p.second, i)));}mq.enque(i, x);if (i - D >= 0)mq.deque(i - D);}ans.first *= -K;printf("%lld\n", ans.first);if (ans.first > 0)printf("%d %d\n", ans.second.first, ans.second.second);}return 0;}