結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-12-16 14:31:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 1,000 ms |
コード長 | 2,662 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 176,944 KB |
実行使用メモリ | 87,380 KB |
最終ジャッジ日時 | 2024-07-20 00:02:46 |
合計ジャッジ時間 | 4,884 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54, from main.cpp:1: In member function 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]', inlined from 'int main()' at main.cpp:123:26: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:202:25: warning: 'selld' may be used uninitialized [-Wmaybe-uninitialized] 202 | { return _M_insert(__n); } | ~~~~~~~~~^~~~~ main.cpp: In function 'int main()': main.cpp:111:18: note: 'selld' was declared here 111 | ll buyd, selld; | ^~~~~ In member function 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]', inlined from 'int main()' at main.cpp:123:11: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:202:25: warning: 'buyd' may be used uninitialized [-Wmaybe-uninitialized] 202 | { return _M_insert(__n); } | ~~~~~~~~~^~~~~ main.cpp: In function 'int main()': main.cpp:111:12: note: 'buyd' was declared here 111 | ll buyd, selld; | ^~~~
ソースコード
#include "bits/stdc++.h"using namespace std;#define DEBUG(x) cout<<#x<<": "<<x<<endl;#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endltypedef long long ll;#define vi vector<int>#define vl vector<ll>#define vii vector< vector<int> >#define vll vector< vector<ll> >#define vs vector<string>#define pii pair<int,int>#define pis pair<int,string>#define psi pair<string,int>#define pll pair<ll,ll>const int inf = 1000000001;const ll INF = 1e18 * 2;#define MOD 1000000007#define mod 1000000009#define pi 3.14159265358979323846#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };//rmq に使用const ll MAX_N = 1 << 21;int n;vector<pll> dat(2 * MAX_N - 1);vl a(MAX_N);//rmqに使用void init(int k, int l, int r) {if (r - l == 1) {dat[k].first = a[l];dat[k].second = l;}else {int lch = 2 * k + 1, rch = 2 * k + 2;init(lch, l, (l + r) / 2);init(rch, (l + r) / 2, r);if (dat[lch].first >= dat[rch].first) {dat[k] = dat[lch];}else {dat[k] = dat[rch];}}}//k番目の値をaに変更//rmqに使用void update(int k, int a, int v, int l, int r) {if (r - l == 1) {dat[v].first = a;}else {if (k < (l + r) / 2)update(k, a, 2 * v + 1, l, (l + r) / 2);else {update(k, a, 2 * v + 2, (l + r) / 2, r);}if (dat[2*v+1].first >= dat[2*v+2].first) {dat[k] = dat[2*v+1];}else {dat[k] = dat[2*v+2];}}}//rmqに使用//[a,b)の最小値を求める//後ろのほうの引数は計算の簡単のための引数//kは接点の番号,l,rはその接点が[l,r)に対応していることを表す//従って、外からはquery(a,b,0,0,n)としてよぶpll query(int a, int b, int k, int l, int r) {if (r <= a || b <= l) {return pll(-1, inf);}if (a <= l && r <= b) {return dat[k];}else {pll ul = query(a, b, k * 2 + 1, l, (l + r) / 2);pll ur = query(a, b, k * 2 + 2, (l + r) / 2, r);if (ul.first >= ur.first) {return ul;}else {return ur;}}}int main() {int d, k, i, j;cin >> n >> d >> k;vector<pll> vp;for (i = 0; i < n; i++) {cin >> a[i];vp.push_back(pll(a[i], i));}sort(vp.begin(), vp.end());init(0, 0, n);ll ans = -INF;ll buyd, selld;for (i = 0; i < n; i++) {ll buy = a[i];pll sell = query(i, min(i + d + 1, n), 0, 0, n);if (ans < (sell.first - buy) * k) {buyd = i;selld = sell.second;ans = (sell.first - buy)*k;}}cout << ans << endl;if (ans) {cout << buyd << " " << selld << endl;}}