結果
問題 | No.489 株に挑戦 |
ユーザー | freecss00 |
提出日時 | 2017-02-27 21:57:03 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 37 ms / 1,000 ms |
コード長 | 3,519 bytes |
コンパイル時間 | 1,226 ms |
コンパイル使用メモリ | 96,164 KB |
実行使用メモリ | 4,960 KB |
最終ジャッジ日時 | 2023-09-27 05:31:36 |
合計ジャッジ時間 | 3,099 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
4,960 KB |
testcase_01 | AC | 16 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 29 ms
4,668 KB |
testcase_17 | AC | 4 ms
4,376 KB |
testcase_18 | AC | 16 ms
4,376 KB |
testcase_19 | AC | 13 ms
4,376 KB |
testcase_20 | AC | 30 ms
4,656 KB |
testcase_21 | AC | 8 ms
4,376 KB |
testcase_22 | AC | 4 ms
4,376 KB |
testcase_23 | AC | 17 ms
4,380 KB |
testcase_24 | AC | 37 ms
4,888 KB |
testcase_25 | AC | 1 ms
4,380 KB |
testcase_26 | AC | 35 ms
4,692 KB |
testcase_27 | AC | 34 ms
4,652 KB |
testcase_28 | AC | 1 ms
4,376 KB |
testcase_29 | AC | 1 ms
4,380 KB |
testcase_30 | AC | 36 ms
4,748 KB |
testcase_31 | AC | 35 ms
4,688 KB |
testcase_32 | AC | 19 ms
4,380 KB |
testcase_33 | AC | 34 ms
4,708 KB |
testcase_34 | AC | 30 ms
4,752 KB |
testcase_35 | AC | 12 ms
4,380 KB |
testcase_36 | AC | 5 ms
4,380 KB |
testcase_37 | AC | 20 ms
4,380 KB |
ソースコード
#include<iostream> #include<fstream> #include<sstream> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> #include<string> #include<cmath> #include<cstdio> #include<cassert> using namespace std; #define REP(i,m,n) for(int i=(m); i<(int)(n); i++) #define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--) #define rep(i,n) REP(i,0,n) #define rrep(i,n) RREP(i,0,n) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define aut(r,v) __typeof(v) r = (v) #define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it) #define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it) #define fi first #define se second #define dump(x) cerr << " [L" << __LINE__ << "] " << #x << " = " << (x) << endl; inline void debug(){cerr<<endl;} template<class First, class... Rest> void debug(const First& first, const Rest&... rest){cerr<<first<<" ";debug(rest...);} template<typename T>string join(vector<T>&v, string del=", ") {stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());} template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p) {return o<<"("<<p.first<<", "<<p.second<<")";} template<typename T>ostream& operator<<(ostream& o, vector<T>&v) {if(v.size())o<<"["<<join(v)<<"]";return o;} template<typename T>ostream& operator<<(ostream& o, vector<vector<T> >&vv) {int l=vv.size();if(l){rep(i,l){o<<(i==0?"[ ":",\n ")<<vv[i]<<(i==l-1?" ]":"");}}return o;} template<typename T>ostream& operator<<(ostream& o, const set<T>& st) {vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;} template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m) {each(p,m){o<<(p==m.begin()?"{ ":",\n ")<<*p<<(p==--m.end()?" }":"");}return o;} using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; const double PI = (1*acos(0.0)); const double INF = 0x3f3f3f3f; const double INFL = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-9; const double mod = 1e9 + 7; inline void finput(string filename) { freopen(filename.c_str(), "r", stdin); } struct RMQ{ int n; vector<int> dat; void init(int n_){ n = 1; while(n < n_) n <<= 1; dat = vector<int>(2*n-1, -1); } void update(int k, int a){ int reaf = k+n-1; dat[reaf] = a; while(reaf > 0){ reaf = (reaf-1) / 2; dat[reaf] = max(dat[reaf*2+1], dat[reaf*2+2]); } } int search(int a, int b, int k, int l, int r){ if(b <= l || r <= a) return -1; if(a <= l && r <= b) return dat[k]; else{ int rl = search(a, b, 2*k+1, l, (l+r)/2); int rr = search(a, b, 2*k+2, (l+r)/2, r); return max(rl, rr); } } int query(int a, int b){ return search(a, b+1, 0, 0, n); } }; vi x; int main(){ ios_base::sync_with_stdio(0); // finput("./input"); ll N, D, K; cin >> N >> D >> K; RMQ rmq; rmq.init(N); rep(i, N){ int _x; cin >> _x; x.push_back(_x); rmq.update(i, _x); } ll ma = -1; int j = -1, k = -1; rep(i,N){ int m = rmq.query(i, min(i+D, N)); if(ma < m - x[i]){ ma = m - x[i]; j = i; } } REP(i,j,min(j+D+1,N)) if(x[i] - x[j] == ma){ k = i; break; } cout << ma*K << endl; if(ma != 0) cout << j << " " << k << endl; return 0; }