結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:45:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 38 ms / 1,000 ms |
コード長 | 1,709 bytes |
コンパイル時間 | 897 ms |
コンパイル使用メモリ | 83,732 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 22:56:28 |
合計ジャッジ時間 | 2,413 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:64:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | scanf("%d", &x[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream>#include <fstream>#include <cstdio>#include <cmath>#include <vector>#include <cstring>#include <string>#include <set>#include <map>#include <stack>#include <queue>#include <algorithm>using namespace std;#define REP(i,n) for(int i=0; i<n; ++i)#define FOR(i,a,b) for(int i=a; i<=b; ++i)#define FORR(i,a,b) for (int i=a; i>=b; --i)#define ALL(c) (c).begin(), (c).end()typedef long long ll;typedef vector<int> VI;typedef vector<ll> VL;typedef vector<VI> VVI;typedef pair<int,int> P;typedef pair<ll,ll> PL;#define INF 1e9const int MAX_N = 200010;int n, width;int dat[MAX_N*4];void init(){width = 1;while(width<n) width*=2;REP(i,2*width-1) dat[i] = INF;}void update(int i, int x){i += width-1;dat[i] = x;while (i>0){i = (i-1)/2;dat[i] = min(dat[i*2+1],dat[i*2+2]);}}int query(int a, int b, int k, int l, int r){if (r<=a || b<=l) return INF;if (a<=l && r<=b) return dat[k];int vl = query(a,b,k*2+1,l,(l+r)/2);int vr = query(a,b,k*2+2,(l+r)/2,r);return min(vl,vr);}int main() {int d;ll kabu;cin >> n >> d >> kabu;init();VI x(n);REP(i,n){scanf("%d", &x[i]);update(i, x[i]);}ll ans = 0;int j, k;REP(i,n){int mi = query(max(0, i-d), i+1, 0, 0, width);if (x[i] - mi > ans){ans = x[i] - mi;k = i;}}if (ans == 0){cout << 0 << endl;return 0;}FOR(i,max(0,k-d),k){if (x[i] == x[k] - ans){j = i;break;}}ans *= kabu;printf("%lld\n%d %d\n", ans, j, k);return 0;}