結果

問題 No.2659 Manga App
ユーザー SimpleCloudSimpleCloud
提出日時 2024-03-16 19:11:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,113 ms / 6,000 ms
コード長 2,584 bytes
コンパイル時間 1,561 ms
コンパイル使用メモリ 182,896 KB
実行使用メモリ 253,312 KB
最終ジャッジ日時 2024-09-30 04:33:07
合計ジャッジ時間 12,622 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 548 ms
128,768 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 19 ms
6,820 KB
testcase_13 AC 10 ms
6,816 KB
testcase_14 AC 268 ms
62,592 KB
testcase_15 AC 55 ms
18,560 KB
testcase_16 AC 245 ms
59,264 KB
testcase_17 AC 56 ms
17,152 KB
testcase_18 AC 163 ms
45,056 KB
testcase_19 AC 4 ms
6,820 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 45 ms
12,672 KB
testcase_22 AC 58 ms
17,280 KB
testcase_23 AC 483 ms
114,432 KB
testcase_24 AC 42 ms
12,416 KB
testcase_25 AC 78 ms
19,200 KB
testcase_26 AC 3 ms
6,820 KB
testcase_27 AC 56 ms
13,824 KB
testcase_28 AC 429 ms
101,120 KB
testcase_29 AC 102 ms
26,880 KB
testcase_30 AC 228 ms
50,560 KB
testcase_31 AC 19 ms
6,816 KB
testcase_32 AC 1,113 ms
253,312 KB
testcase_33 AC 1,096 ms
253,312 KB
testcase_34 AC 228 ms
54,912 KB
testcase_35 AC 373 ms
86,784 KB
testcase_36 AC 446 ms
97,152 KB
testcase_37 AC 372 ms
87,040 KB
testcase_38 AC 372 ms
87,168 KB
testcase_39 AC 371 ms
87,168 KB
testcase_40 AC 383 ms
87,424 KB
testcase_41 AC 427 ms
88,448 KB
testcase_42 AC 408 ms
90,752 KB
testcase_43 AC 417 ms
93,568 KB
testcase_44 AC 436 ms
97,408 KB
testcase_45 AC 443 ms
97,280 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void solve()':
main.cpp:77:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   77 |                 for(auto [j,v]:f[i]){
      |                          ^
main.cpp:80:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   80 |                         auto [tt,cost]=tim[i+1][c];
      |                              ^
main.cpp:86:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   86 |                         auto [p,jj]=to[i+1][c];jj+=j;
      |                              ^

ソースコード

diff # 

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second
#define int long long

using namespace std;

inline ll read(){
	ll x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=2005;
int n;
ll m,a[N],x,y,d;

map<ll,ll>f[N];
pair<ll,ll>tim[N][2];
pair<int,ll>to[N][2];
void solve(){
	n=read()-1,x=read(),y=read(),m=read(),d=x+y;
	for(int i=1;i<=n;i++)a[i]=read();
	
	auto calc=[&](int st,int c){
		ll cur=0,cost=0;
		if(c==1)cur=x;
//		cout<<"calc "<<st<<" "<<c<<endl;
		for(int i=st;i<=n;i++){
//			cout<<" now i = "<<i<<" cur,cost = "<<cur<<" "<<cost<<endl;
			cur+=a[i];ll z=cur%d-x;
			if(z>0)cost+=z,cur-=z;
		}
//		cout<<"End :: cur,cost = "<<cur<<" "<<cost<<endl;
		if(c==1)cur-=x;
		return mk(cur,cost);
	};
	auto getp=[&](int st,int c){
		ll cur=0;
		if(c==1)cur=x;
		for(int i=st;i<=n;i++){
			cur+=a[i];
			if(cur%d>x)return mk(i,cur-(c==1?x:0ll));
		}
		return mk(n+1,cur-(c==1?x:0ll));
	};
	for(int i=n+1;i>=1;i--)for(int c=0;c<=1;c++)tim[i][c]=calc(i,c),to[i][c]=getp(i,c);
	
	f[0][0]=0;
	auto Cmin=[&](int i,ll j,ll v){
		auto it=f[i].find(j);
		if(it!=f[i].end())cmin((*it).second,v);
		else f[i][j]=v;
	};
	ll ans=1e18;
	for(int i=0;i<=n;i++){
		for(auto [j,v]:f[i]){
			int c=0;if(j%d==x)c=1;
//			cout<<"f "<<i<<" "<<j<<" = "<<v<<endl;
			auto [tt,cost]=tim[i+1][c];
			if(cost+v<=m){
				ll ret=m-cost-v,cur=j+max(0ll,tt-ret);
				if(cur%d>x)cur+=(d-cur%d);cmin(ans,cur);
//				cout<<" tt = "<<tt<<" cost = "<<cost<<" -> ans = "<<ans<<endl;
			}
			auto [p,jj]=to[i+1][c];jj+=j;
			if(p==n+1)continue;
//			cout<<" -> p = "<<p<<" jj = "<<jj<<endl;
			assert(jj%d>x);
			Cmin(p,(ll)((jj/d)+1)*d,v);
			Cmin(p,jj-((jj%d)-x),v+(jj%d-x));
		}
	}
	
	cout<<ans<<endl;
	
	for(int i=0;i<=n+1;i++)f[i].clear(),tim[i][0]=tim[i][1]=mk(0,0),to[i][0]=to[i][1]=mk(0,0);
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	int tt=1;
//	int Id=read(),tt=read();
	while(tt--)solve();

	return 0;
}
0