結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-25 00:30:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 99 ms / 1,000 ms |
コード長 | 2,900 bytes |
コンパイル時間 | 1,314 ms |
コンパイル使用メモリ | 164,856 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-07-19 23:19:01 |
合計ジャッジ時間 | 4,100 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF 1001000100010001000#define MOD 1000000007#define RMQ_SIZE 262144#define EPS 1e-10#define int long long#define rep(i, N) for (int i = 0; i < N; i++)#define Rep(i, N) for (int i = 1; i < N; i++)#define For(i, a, b) for (int i = (a); i < (b); i++)#define pb push_back#define mp make_pair#define i_i pair<int, int>#define vi vector<int>#define vvi vector<vi >#define vb vector<bool>#define vvb vector<vb >#define vp vector< i_i >#define all(a) (a).begin(), (a).end()#define Int(x) int x; scanf("%lld", &x);#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);//int dxy[5] = {0, 1, 0, -1, 0};// assignclass segtree{private:i_i dfs(int a,int b,int k,int l,int r){//* 要求範囲を含まないレンジの探索.if (r <= a || b <= l) {return mp(INF, -1);}//* 木のレンジが要求範囲以下になる時.if (a <= l && r <= b) {return tree[k];}int m = (l+r)/2;return min(dfs(a, b, k*2+1, l, m), dfs(a, b, k*2+2, m, r));}i_i min(i_i a, i_i b){if (a.first < b.first) {return a;} else if (a.first > b.first) {return b;} else if (a.second < b.second) {return a;} else {return b;}}public:int size;i_i *tree;segtree(int c) {size = 262144;tree = (i_i *)malloc(sizeof(i_i)*size);for (int i = 0; i < size; i++) {tree[i] = mp(c, i);}}i_i getMin(int right, int left){return dfs(right, left, 0, 0, RMQ_SIZE/2);}void update(int pos, int value){pos += (RMQ_SIZE/2 -1);tree[pos].first = value;while (pos) {pos = (pos-1)/2;tree[pos] = min(tree[pos*2+1], tree[pos*2+2]);}}};signed main(){int a, b, c;cin >> a >> b >> c;vi input(a, 0);segtree mi(INF), ma(-INF);rep(i, a) {cin >> input[i];mi.update(i, input[i]);ma.update(i, -input[i]);}int ans = 0;i_i ret;rep(i, a) {i_i d = mi.getMin(i, min(i+b+1, a)),e = ma.getMin(i, min(i+b+1, a));//cout << d.second << " " << e.second << endl;if (ans < -e.first - input[i]) {ans = -e.first - input[i];ret.first = i;ret.second = e.second - 262144/2 + 1;}}if (ans) {cout << ans * c << endl;cout << ret.first << " " << ret.second << endl;} else {cout << 0 << endl;}return 0;}