結果

問題 No.409 ダイエット
ユーザー Guowen RongGuowen Rong
提出日時 2024-11-17 19:10:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,502 bytes
コンパイル時間 3,822 ms
コンパイル使用メモリ 196,472 KB
実行使用メモリ 27,136 KB
最終ジャッジ日時 2024-11-17 19:10:50
合計ジャッジ時間 9,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 81 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define Add(x, y) (x + y >= mod) ? (x + y - mod) : (x + y)
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define pii pair<ll, pair<ll, ll>>
#define iip pair<pair<ll, ll>, ll>
#define ppii pair<pair<ll, ll>, pair<ll, ll>>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define full(l, r, x) for(auto it = l; it != r; ++it) (*it) = x
#define Full(a) memset(a, 0, sizeof(a))
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define For(i, l, r) for(register int i = l; i <= r; ++i)
#define _For(i, l, r) for(register int i = r; i >= l; --i)
using namespace std;
using namespace __gnu_pbds;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 3e5 + 10;
const db eps = 1e-9;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
ll n, a, b, w;
ll s[N], d[N], T[N];
namespace Tree{
	int cnt;
	struct Line{
		db k, b;
	}h[N];
	struct Node{
		int l, r;
		int id;
	}X[N << 2];
	int check(db x, db y){
	    if(x - y > eps)
		  return 1;
	    if(y - x > eps)
		  return -1;
	    return 0;
	} 
	inline db Fun(int x, int id){
		return h[id].k * x + h[id].b;
	}
	inline void build(int k, int l, int r){
		X[k].l = l, X[k].r = r;
		if(l == r)
		  return ;
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
	}
	inline void update(int k, int l, int r, int id){
		if(!id)
		  return ;
		int mid = (X[k].l + X[k].r) >> 1;
		if(X[k].l == l && r == X[k].r){
			int op = check(Fun(mid, id), Fun(mid, X[k].id));
			if(op == -1 || (!op && id < X[k].id))
			  swap(X[k].id, id);
			op = check(Fun(l, id), Fun(l, X[k].id));
			if(op == -1 || (!op && id < X[k].id))
			  update(k << 1, l, mid, id);
			op = check(Fun(r, id), Fun(r, X[k].id));
			if(op == -1 || (!op && id < X[k].id))
			  update(k << 1 | 1, mid + 1, r, id);
			return ;
		}
		if(r <= mid)
		  update(k << 1, l, r, id);
		else if(l > mid)
		  update(k << 1 | 1, l, r, id);
		else{
			update(k << 1, l, mid, id);
			update(k << 1 | 1, mid + 1, r, id);
		}
	}
	inline int query(int k, int i){
		if(X[k].l == i && i == X[k].r)
		  return X[k].id;
		db t = Fun(i, X[k].id);
		int mid = (X[k].l + X[k].r) >> 1, h = 0;
		if(i <= mid)
		  h = query(k << 1, i);
		else
		  h = query(k << 1 | 1, i);
		if(Fun(i, h) < t)
		  return h;
		if(!check(Fun(i, h), t))
		  return min(X[k].id, h);
		return X[k].id;
	}
	inline void add(db k, db b){
		h[++cnt] = {k, b};
		update(1, 0, n + 1, cnt);
	}
	inline ll ask(int x){
		int id = query(1, x);
		return Fun(x, id);
	}
};
bool End;
int main(){
	n = read(), a = read(), b = read(), w = read();
	Tree::h[0].b = 1e18;
	Tree::build(1, 0, n + 1);
	s[0] = s[1] = w;
	T[0] = s[0] + a;
	Tree::add(0, T[0]);
	for(ll i = 2; i <= n + 1; ++i){
		d[i] = read();
		s[i] = Tree::ask(i) + (i * (i - 1) >> 1) * b - i * a;
		s[i] = min(s[i], s[i - 1] + d[i]);
		T[i - 1] = s[i - 1] + d[i] + i * a + (i * (i - 1) >> 1) * b;
		Tree::add(-(i - 1) * b, T[i - 1]);
	}
	write(s[n + 1]);
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}
0