#961371 (C++14) No.2659 Manga App

提出ソース

結果

問題	No.2659 Manga App
ユーザー	SimpleCloud
提出日時	2024-03-16 19:11:12
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,259 ms / 6,000 ms
コード長	2,584 bytes
コンパイル時間	2,196 ms
コンパイル使用メモリ	182,116 KB
実行使用メモリ	253,440 KB
最終ジャッジ日時	2024-03-16 19:11:28
合計ジャッジ時間	15,166 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	3 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	615 ms 128,896 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	22 ms 6,676 KB
testcase_13	AC	11 ms 6,676 KB
testcase_14	AC	309 ms 62,720 KB
testcase_15	AC	63 ms 18,688 KB
testcase_16	AC	306 ms 59,264 KB
testcase_17	AC	66 ms 17,280 KB
testcase_18	AC	183 ms 45,184 KB
testcase_19	AC	5 ms 6,676 KB
testcase_20	AC	2 ms 6,676 KB
testcase_21	AC	52 ms 12,800 KB
testcase_22	AC	68 ms 17,408 KB
testcase_23	AC	511 ms 114,560 KB
testcase_24	AC	52 ms 12,544 KB
testcase_25	AC	89 ms 19,328 KB
testcase_26	AC	3 ms 6,676 KB
testcase_27	AC	65 ms 13,824 KB
testcase_28	AC	486 ms 101,248 KB
testcase_29	AC	118 ms 26,880 KB
testcase_30	AC	246 ms 50,688 KB
testcase_31	AC	21 ms 6,676 KB
testcase_32	AC	1,259 ms 253,440 KB
testcase_33	AC	1,250 ms 253,440 KB
testcase_34	AC	261 ms 54,912 KB
testcase_35	AC	413 ms 86,912 KB
testcase_36	AC	488 ms 97,280 KB
testcase_37	AC	422 ms 87,168 KB
testcase_38	AC	421 ms 87,296 KB
testcase_39	AC	418 ms 87,296 KB
testcase_40	AC	431 ms 87,424 KB
testcase_41	AC	434 ms 88,576 KB
testcase_42	AC	449 ms 90,880 KB
testcase_43	AC	480 ms 93,696 KB
testcase_44	AC	493 ms 97,408 KB
testcase_45	AC	504 ms 97,408 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;
      |                              ^

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード