結果

問題 No.489 株に挑戦
ユーザー koba-e964
提出日時 2017-02-24 23:26:29
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 44 ms / 1,000 ms
コード長 3,089 bytes
コンパイル時間 1,267 ms
コンパイル使用メモリ 93,304 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-07-19 23:06:31
合計ジャッジ時間 2,593 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In static member function ‘static int SparseTable<T, BiOp>::top_bit(int) [with T = long long int; BiOp = mymax]’:
main.cpp:71:7: warning: ‘v’ is used uninitialized [-Wuninitialized]
   71 |     c = *(const int *) &v;  // OR, for portability:  memcpy(&c, &v, sizeof c);
      |     ~~^~~~~~~~~~~~~~~~~~~
main.cpp:68:17: note: ‘v’ declared here
   68 |     const float v = t; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)
      |                 ^

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;
/*
* Sparse Table.
* BiOp should be the type of a binary operator which is
* associative, commutative and idempotent.
* (For example, min and gcd satisfy them.)
* Header Requirement: vector, cassert
* Verified by: AtCoder ARC023 D (http://arc023.contest.atcoder.jp/submissions/960757)
*/
template<class T, class BiOp>
class SparseTable {
private:
BiOp biop;
std::vector<std::vector<T> > st;
void create_sparse_table(int n, const std::vector<T> &lcp) {
int h = 1;
while ((1 << h) < n) {
++h;
}
st = std::vector<std::vector<T> >(h + 1, std::vector<T>(n));
for (int i = 0; i < n; ++i) {
st[0][i] = lcp[i];
}
for (int j = 1; j <= h; ++j) {
for (int i = 0; i <= n - (1 << j); ++i) {
st[j][i] = biop(st[j - 1][i], st[j - 1][i + (1 << (j-1))]);
}
}
}
/*
* Reference: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogFloat
* Please be aware that it only works well in case of 1 <= t <= 2^24.
*/
static int top_bit(int t) {
const float v = t; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)
int c; // 32-bit int c gets the result;
c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c);
return (c >> 23) - 127;
}
public:
/*
* Initializes this sparse table. O(n log n) where n = ary.size().
*/
SparseTable(BiOp biop, const std::vector<T> &ary): biop(biop) {
create_sparse_table(ary.size(), ary);
}
/*
* Computes biop(ary[f], ary[f+1], ..., ary[s]). O(1).
* Note: the interval is inclusive.
*/
T query(int f, int s) const {
assert (f <= s);
int diff = top_bit(s + 1 - f);
return biop(st[diff][f], st[diff][s + 1 - (1 << diff)]);
}
};
struct mymax {
ll operator()(ll x, ll y) const {
return max(x, y);
}
};
int main(void){
int n, d;
ll k;
cin >> n >> d >> k;
VL x(n);
REP(i, 0, n) {
cin >> x[i];
}
SparseTable<ll, mymax> spt(mymax(), x);
ll ma = 0;
int mini1 = -1;
REP(i, 0, n) {
ll a = x[i];
ll y = spt.query(i, min(i + d, n - 1));
if (y <= a) { continue; }
ll t = y - a;
if (ma < t) {
ma = t;
mini1 = i;
}
}
if (ma == 0) {
cout << 0 << endl;
return 0;
}
cout << ma * k << endl;
cout << mini1 << " ";
int mini2 = -1;
REP(i, mini1, min(mini1 + d + 1, n)) {
if (ma + x[mini1] == x[i]) {
mini2 = i;
break;
}
}
assert (mini2 >= 0);
cout << mini2 << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0