結果
問題 | No.489 株に挑戦 |
ユーザー | IL_msta |
提出日時 | 2017-02-24 23:35:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,853 bytes |
コンパイル時間 | 1,979 ms |
コンパイル使用メモリ | 129,296 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-10 23:27:32 |
合計ジャッジ時間 | 3,200 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 24 ms
5,504 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 25 ms
5,632 KB |
testcase_21 | AC | 6 ms
5,376 KB |
testcase_22 | AC | 4 ms
5,376 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 24 ms
5,504 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 25 ms
5,632 KB |
testcase_31 | AC | 23 ms
5,632 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 14 ms
5,376 KB |
ソースコード
//以下を参考にした//https://yukicoder.me/wiki/auto_vectorization#ifdef __GNUC__#pragma GCC optimize ("O3")#pragma GCC target ("avx")#endif#define _USE_MATH_DEFINES#include <iostream>#include <iomanip>#include <stdio.h>#include <sstream>#include <algorithm>#include <cmath>#include <string>#include <cstring>#include <vector>#include <valarray>//#include <array>//x C++ (G++ 4.6.4)#include <queue>#include <complex>#include <set>#include <map>#include <stack>#include <list>#include <cassert>//assert();#include <fstream>#include <random>/////////#define REP(i, x, n) for(int i = x; i < n; ++i)#define rep(i,n) REP(i,0,n)/////////typedef long long LL;typedef long double LD;typedef unsigned long long ULL;#define PII pair<int,int>/////////using namespace::std;// 最大公約数template<class T>inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}//inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}// 最小公倍数template<class T>inline T lcm(T a, T b){return a / gcd(a, b) * b;}//inline T lcm(T a, T b){return a * b / gcd(a, b);}////////////////////////////////class segment{int n; //nは2のべき乗int MAX_VAL;vector< pair<int,int> > dat;//first:val second:indexpublic:int getN(){return n;}void init(int N,int MAX_num){//N:要素数,最大値MAX_VAL = MAX_num;n = 2;while(n < N ){n <<= 1;}dat.assign(2*n-1,pair<int,int>(MAX_VAL,-1));}void update(int i,int x){i += n-1;//葉のノード番号dat[i] = pair<int,int>(x,i -(n-1));//値を更新,indexwhile(i>0){i = (i-1)/2;if( dat[i*2+1].first <= dat[i*2+2].first ){dat[i] = dat[i*2+1];}else{dat[i] = dat[i*2+2];}}}//query(a,b,0,0,n)pair<int,int> query(int a,int b,int k,int l,int r){if(r<=a || b<=l){return pair<int,int>(MAX_VAL,-1);//交差しない}if(a<=l && r<=b)return dat[k];else{pair<int,int> vl = query(a,b,k*2+1,l,(l+r)/2);pair<int,int> vr = query(a,b,k*2+2,(l+r)/2,r);if( vl.first <= vr.first ){return vl;}else{return vr;}}}};void solve(){LL N,D,K;cin >> N >> D >> K;segment seg;seg.init((int)N,1000001);vector<int> X((int)N+1);for(int i=0;i<N;++i){cin >> X[i];seg.update(i,-X[i]);}LL MAX = -1;int posL = -1;int posR = -1;for(int i=0;i<N;++i){pair<int,int> res = seg.query(i,i+(int)D,0,0,(int)N);LL temp = -res.first;temp -= X[i];if( temp > MAX ){MAX = temp;posL = i;posR = res.second;}}LL ans = MAX * K;if( MAX > 0 ){cout << ans << endl;cout << posL << " " << posR << endl;}else{cout << 0 << endl;}}signed main(void){std::cin.tie(0);std::ios::sync_with_stdio(false);//std::cout << std::fixed;//小数を10進数表示//cout << setprecision(16);//小数点以下の桁数を指定solve();}