結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-12-27 20:55:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 91 ms / 1,000 ms |
コード長 | 2,335 bytes |
コンパイル時間 | 1,023 ms |
コンパイル使用メモリ | 92,896 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-07-20 00:02:50 |
合計ジャッジ時間 | 3,221 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | #define GI(i) (scanf("%d",&i)) | ~~~~~~^~~~~~~~~~ main.cpp:71:5: note: in expansion of macro ‘GI’ 71 | GI(N);GI(D);GI(K); | ^~ main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | #define GI(i) (scanf("%d",&i)) | ~~~~~~^~~~~~~~~~ main.cpp:71:11: note: in expansion of macro ‘GI’ 71 | GI(N);GI(D);GI(K); | ^~ main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | #define GI(i) (scanf("%d",&i)) | ~~~~~~^~~~~~~~~~ main.cpp:71:17: note: in expansion of macro ‘GI’ 71 | GI(N);GI(D);GI(K); | ^~ main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | #define GI(i) (scanf("%d",&i)) | ~~~~~~^~~~~~~~~~ main.cpp:74:9: note: in expansion of macro ‘GI’ 74 | GI(x[i]); | ^~
ソースコード
#include <iostream>#include <stack>#include <cstdio>#include <cstdlib>#include <cmath>#include <string>#include <vector>#include <queue>#include <map>#include <set>#include <tuple>#include <algorithm>#include <functional>#include <cstring>#include <limits.h>#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)#define REP(i,n) FOR(i,0,n)#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)#define SZ(i) ((int)i.size())#define GI(i) (scanf("%d",&i))#define GLL(i) (scanf("%lld",&i))#define GD(i) (scanf("%lf",&i))#define PB push_back#define MP make_pair#define MT make_tuple#define GET0(x) (get<0>(x))#define GET1(x) (get<1>(x))#define GET2(x) (get<2>(x))#define ALL(X) (X).begin(),(X).end()#define LLMAX (1LL<<60)#define LLMIN -(1LL<<60)#define IMAX (1<<30)#define IMIN -(1<<30)typedef long long LL;using namespace std;#define MAX 200000class RangeMaxPointChange{public:int N, dat[2*MAX];RangeMaxPointChange(int n) {N = 1;while(N < n) N *= 2;for(int i = 0; i < 2*N-1; i++)dat[i] = IMIN;}// update k th elementvoid update(int k, int a) {k += N-1; // leafdat[k] = a;while(k > 0) {k = (k - 1) / 2;dat[k] = max(dat[k*2+1], dat[k*2+2]);}}// min [a, b)int query(int a, int b) { return query(a, b, 0, 0, N); }int query(int a, int b, int k, int l, int r) {if(r <= a or b <= l) return IMIN;if(a <= l and r <= b) return dat[k];int m = (l + r) / 2;return max(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));}};int N,D,K,x[200000];map<int,vector<int> > id;int main(void){GI(N);GI(D);GI(K);RangeMaxPointChange seg(N);REP(i,N){GI(x[i]);id[x[i]].PB(i);seg.update(i,x[i]);}LL m=0;int j,k;REP(i,N){int b = seg.query(i,min(N,i+D+1));// printf("i=%d b=%d D=%d\n",i,b,D);if(m < (LL)(b - x[i]) * (LL)K){m = (LL)(b - x[i]) * (LL)K;j = i;k = *lower_bound(ALL(id[b]),i+1);}}if(m==0)printf("%lld\n",m);elseprintf("%lld\n%d %d\n",m,j,k);return 0;}