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

提出ソース

結果

問題	No.409 ダイエット
ユーザー	Guowen Rong
提出日時	2024-11-17 19:16:41
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	106 ms / 2,000 ms
コード長	3,477 bytes
コンパイル時間	4,236 ms
コンパイル使用メモリ	197,572 KB
実行使用メモリ	27,136 KB
最終ジャッジ日時	2024-11-17 19:16:51
合計ジャッジ時間	9,359 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 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	2 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	2 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	1 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	3 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	3 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	3 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	3 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB
testcase_40	AC	3 ms 5,248 KB
testcase_41	AC	3 ms 5,248 KB
testcase_42	AC	3 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	5 ms 5,248 KB
testcase_47	AC	3 ms 5,248 KB
testcase_48	AC	2 ms 5,248 KB
testcase_49	AC	3 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	2 ms 5,248 KB
testcase_52	AC	3 ms 5,248 KB
testcase_53	AC	3 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	49 ms 15,104 KB
testcase_56	AC	55 ms 26,752 KB
testcase_57	AC	106 ms 27,136 KB
testcase_58	AC	42 ms 11,392 KB
testcase_59	AC	63 ms 16,512 KB
testcase_60	AC	37 ms 10,880 KB
testcase_61	AC	84 ms 19,712 KB
testcase_62	AC	92 ms 26,240 KB
testcase_63	AC	86 ms 19,456 KB
testcase_64	AC	51 ms 14,848 KB
testcase_65	AC	97 ms 23,680 KB
testcase_66	AC	98 ms 26,880 KB
testcase_67	AC	71 ms 18,048 KB
testcase_68	AC	63 ms 16,384 KB
testcase_69	AC	86 ms 19,328 KB
testcase_70	AC	80 ms 18,816 KB
testcase_71	AC	46 ms 11,648 KB
testcase_72	AC	102 ms 26,880 KB
testcase_73	AC	97 ms 19,840 KB
testcase_74	AC	59 ms 16,000 KB
testcase_75	AC	95 ms 21,760 KB
testcase_76	AC	69 ms 17,152 KB
testcase_77	AC	47 ms 11,520 KB
testcase_78	AC	54 ms 15,360 KB
testcase_79	AC	42 ms 11,008 KB
testcase_80	AC	94 ms 26,240 KB
testcase_81	AC	95 ms 19,840 KB
testcase_82	AC	68 ms 17,152 KB
testcase_83	AC	72 ms 17,792 KB
testcase_84	AC	65 ms 16,256 KB
testcase_85	AC	8 ms 5,248 KB
testcase_86	AC	62 ms 16,128 KB
testcase_87	AC	80 ms 18,816 KB
testcase_88	AC	35 ms 10,240 KB
testcase_89	AC	63 ms 17,280 KB
testcase_90	AC	32 ms 9,984 KB
testcase_91	AC	69 ms 17,792 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 = 3e5 + 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{
	int cnt;
	struct Line{
		ll k, b;
	}h[N];
	struct Node{
		int l, r;
		int id;
	}X[N << 2];
	int check(ll x, ll y){
	    if(x - y > 0)
		  return 1;
	    if(y - x > 0)
		  return -1;
	    return 0;
	} 
	inline ll 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(ll k, ll 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;
}

yukicoder

結果

テストケース

ソースコード