#1027457 (C++14) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	Guowen Rong
提出日時	2024-11-17 19:15:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	100 ms / 2,000 ms
コード長	3,481 bytes
コンパイル時間	1,958 ms
コンパイル使用メモリ	196,676 KB
実行使用メモリ	39,424 KB
最終ジャッジ日時	2024-11-17 19:15:32
合計ジャッジ時間	7,187 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	3 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	3 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	3 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	3 ms 5,248 KB
testcase_38	AC	3 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB
testcase_40	AC	3 ms 5,248 KB
testcase_41	AC	4 ms 5,248 KB
testcase_42	AC	4 ms 5,248 KB
testcase_43	AC	3 ms 5,248 KB
testcase_44	AC	3 ms 5,248 KB
testcase_45	AC	3 ms 5,248 KB
testcase_46	AC	3 ms 5,248 KB
testcase_47	AC	3 ms 5,248 KB
testcase_48	AC	3 ms 5,248 KB
testcase_49	AC	3 ms 5,248 KB
testcase_50	AC	3 ms 5,248 KB
testcase_51	AC	3 ms 5,248 KB
testcase_52	AC	3 ms 5,248 KB
testcase_53	AC	3 ms 5,248 KB
testcase_54	AC	3 ms 5,248 KB
testcase_55	AC	49 ms 21,120 KB
testcase_56	AC	52 ms 39,040 KB
testcase_57	AC	97 ms 39,424 KB
testcase_58	AC	41 ms 14,336 KB
testcase_59	AC	62 ms 22,656 KB
testcase_60	AC	38 ms 13,824 KB
testcase_61	AC	98 ms 25,728 KB
testcase_62	AC	95 ms 38,656 KB
testcase_63	AC	88 ms 25,728 KB
testcase_64	AC	47 ms 20,736 KB
testcase_65	AC	95 ms 29,824 KB
testcase_66	AC	97 ms 39,040 KB
testcase_67	AC	73 ms 24,192 KB
testcase_68	AC	61 ms 22,656 KB
testcase_69	AC	87 ms 25,472 KB
testcase_70	AC	82 ms 25,088 KB
testcase_71	AC	44 ms 14,848 KB
testcase_72	AC	100 ms 39,168 KB
testcase_73	AC	92 ms 25,984 KB
testcase_74	AC	56 ms 22,272 KB
testcase_75	AC	91 ms 27,904 KB
testcase_76	AC	79 ms 23,296 KB
testcase_77	AC	50 ms 14,720 KB
testcase_78	AC	54 ms 21,504 KB
testcase_79	AC	42 ms 14,080 KB
testcase_80	AC	95 ms 38,528 KB
testcase_81	AC	91 ms 25,856 KB
testcase_82	AC	67 ms 23,296 KB
testcase_83	AC	73 ms 24,064 KB
testcase_84	AC	65 ms 22,400 KB
testcase_85	AC	9 ms 5,760 KB
testcase_86	AC	62 ms 22,272 KB
testcase_87	AC	83 ms 25,088 KB
testcase_88	AC	35 ms 13,312 KB
testcase_89	AC	63 ms 23,424 KB
testcase_90	AC	31 ms 13,184 KB
testcase_91	AC	67 ms 23,936 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 4e5 + 10;
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{
	ll cnt;
	struct Line{
		ll k, b;
	}h[N];
	struct Node{
		ll l, r;
		ll id;
	}X[N << 2];
	ll check(ll x, ll y){
	    if(x - y > 0)
		  return 1;
	    if(y - x > 0)
		  return -1;
	    return 0;
	} 
	inline ll Fun(ll x, ll id){
		return h[id].k * x + h[id].b;
	}
	inline void build(ll k, ll l, ll r){
		X[k].l = l, X[k].r = r;
		if(l == r)
		  return ;
		ll mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
	}
	inline void update(ll k, ll l, ll r, ll id){
		if(!id)
		  return ;
		ll mid = (X[k].l + X[k].r) >> 1;
		if(X[k].l == l && r == X[k].r){
			ll 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 ll query(ll k, ll i){
		if(X[k].l == i && i == X[k].r)
		  return X[k].id;
		db t = Fun(i, X[k].id);
		ll 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(ll k, ll b){
		h[++cnt] = {k, b};
		update(1, 0, n + 1, cnt);
	}
	inline ll ask(ll x){
		ll id = query(1, x);
		return Fun(x, id);
	}
};
bool End;
int main(){
//	open("A.in", "A.out");
	n = read(), a = read(), b = read(), w = read();
	Tree::h[0].b = 2e18;
	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;
}

yukicoder

結果

テストケース

ソースコード