Submission #684124

#	Time	Username	Problem	Language	Result	Execution time	Memory
684124		jamezzz	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	1699 ms	1740 KiB

vault

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 1005
#define maxv 200005

int n,m,v,up[maxn],num[maxn];
ll l,a[maxn],take[maxn],dp[maxv];

void update(int num,int val,int cost){
	int cnt=0;
	while(num){
		int iter=1;
		if(num%2==0)iter=2;
		num=(num-1)/2;
		for(int i=0;i<iter;++i){
			if(val>=0){
				for(int i=v;i>=-v;--i){
					int cur=val*(1<<cnt);
					if(i+cur<=v)mxto(dp[i+cur+v],dp[i+v]+cost*(1<<cnt));
				}
			}
			else{
				for(int i=-v;i<=v;++i){
					int cur=val*(1<<cnt);
					if(-v<=i+cur)mxto(dp[i+cur+v],dp[i+v]+cost*(1<<cnt));
				}
			}
		}
		++cnt;
	}
}

int main(){
	sf("%d%lld",&m,&l);
	ll tot=0,pos=0;
	n=2*m+1;v=m*m;
	for(int i=0;i<n;++i){
		up[i]=i-m;
		sf("%lld",&a[i]);
		tot+=a[i]*up[i];
		if(up[i]>0)pos+=a[i]*up[i];
	}
	if(pos<l){
		pf("impossible\n");
		exit(0);
	}
	ll cur=0,ans=0;
	if(tot>=l){
		for(int i=0;i<n;++i){
			if(up[i]<=0)take[i]=a[i];
			else take[i]=min(a[i],(l-cur)/up[i]);
			cur+=take[i]*up[i];
			ans+=take[i];
		}
	}
	else{
		for(int i=n-1;i>=0;--i){
			if(up[i]>=0)take[i]=a[i];
			else take[i]=min(a[i],(cur-l)/(-up[i]));
			cur+=take[i]*up[i];
			ans+=take[i];
		}
	}
	assert(l-m<=cur&&cur<=l+m);
	for(int i=-v;i<=v;++i)dp[i+v]=-LINF;
	dp[cur-l+v]=ans;
	for(int i=0;i<n;++i){
		update((int)min((ll)2*m,a[i]-take[i]),up[i],1);
		update((int)min((ll)2*m,take[i]),-up[i],-1);
	}
	if(dp[v]<0)pf("impossible\n");
	else pf("%lld\n",dp[v]);
}

/*
2 5
2 3 1 1 4

3 5
3 1 0 2 0 0 2

1 5
0 0 6
*/

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:92:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  sf("%d%lld",&m,&l);
      |    ^
vault.cpp:97:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   sf("%lld",&a[i]);
      |     ^

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 10 / 10