結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-05-22 20:24:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 43 ms / 1,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 1,562 ms |
コンパイル使用メモリ | 165,232 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-07-19 23:53:15 |
合計ジャッジ時間 | 3,174 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:62:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 62 | REP(i, N) scanf("%d", x + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,a,b) for(int i=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()#define fi first#define se secondtemplate<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }typedef unsigned long long ull;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<int, pii> P;const ll INF = 1ll<<29;const ll MOD = 1000000007;const double EPS = 1e-10;struct SegmentTree {pii init_val;int n;vector<pii> dat;SegmentTree(int _n) {init_val = pii(0, 0);n = 1;while (n < _n) n *= 2;dat.resize(2 * n - 1, init_val);}void update(int k, pii a) {k += n - 1;chmax(dat[k], a);while (k > 0) {k = (k - 1) / 2;dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);}}pii query(int a, int b, int k, int l, int r) {if (r <= a || b <= l) return init_val;if (a <= l && r <= b) return dat[k];return max(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));}pii query(int a, int b) {return query(a, b, 0, 0, n);}};int N, D, K;int x[112345];int main() {cin >> N >> D >> K;REP(i, N) scanf("%d", x + i);SegmentTree seg(N);REP(i, N) seg.update(i, pii(x[i], -i));int ans = 0;pii anspos;REP(i, N - 1) {pii now = seg.query(i + 1, min(N, i + 1 + D));if (chmax(ans, now.fi - x[i])) anspos = pii(i, -now.se);}if (ans == 0) puts("0");else {printf("%lld\n", (ll)ans * K);printf("%d %d\n", anspos.fi, anspos.se);}return 0;}