結果

問題 No.2659 Manga App
コンテスト
ユーザー SimpleCloud
提出日時 2024-03-16 19:11:12
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
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