Submission #684007

# Submission time Handle Problem Language Result Execution time Memory
684007 2023-01-20T03:32:48 Z jamezzz Uplifting Excursion (BOI22_vault) C++17
Compilation error
0 ms 0 KB
#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 1000000007inline 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 200005int 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)iter=2;		num=(num-1)/2;		if(val>=0){			for(int i=v;i>=-v;--i){				int cur=val<<cnt;				if(i+cur<=v)mxto(dp[i+cur+v],dp[i+v]+(cost<<cnt));			}		}		else{			for(int i=-v;i<=v;++i){				int cur=val<<cnt;				if(-v<=i-cur)mxto(dp[i-cur+v],dp[i+v]+(cost<<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;	for(int i=0;i<n;++i){		if(tot>=l){			if(up[i]<=0)take[i]=up[i];			else take[i]=min(a[i],(l-cur)/up[i]);		}		else{			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-v<=cur&&cur<=l+v);	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]==-LINF)pf("impossible\n");	else pf("%lld\n",dp[v]);}

Compilation message

vault.cpp:1:31: warning: extra tokens at end of #include directive
    1 | #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 1000000007inline 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 200005int 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)iter=2;  num=(num-1)/2;  if(val>=0){   for(int i=v;i>=-v;--i){    int cur=val<<cnt;    if(i+cur<=v)mxto(dp[i+cur+v],dp[i+v]+(cost<<cnt));   }  }  else{   for(int i=-v;i<=v;++i){    int cur=val<<cnt;    if(-v<=i-cur)mxto(dp[i-cur+v],dp[i+v]+(cost<<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; for(int i=0;i<n;++i){  if(tot>=l){   if(up[i]<=0)take[i]=up[i];   else take[i]=min(a[i],(l-cur)/up[i]);  }  else{   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-v<=cur&&cur<=l+v); 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]==-LINF)pf("impossible\n"); else pf("%lld\n",dp[v]);}
      |                               ^~~~~~~~~
vault.cpp:1:81: warning: __VA_ARGS__ can only appear in the expansion of a C++11 variadic macro
    1 | #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 1000000007inline 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 200005int 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)iter=2;  num=(num-1)/2;  if(val>=0){   for(int i=v;i>=-v;--i){    int cur=val<<cnt;    if(i+cur<=v)mxto(dp[i+cur+v],dp[i+v]+(cost<<cnt));   }  }  else{   for(int i=-v;i<=v;++i){    int cur=val<<cnt;    if(-v<=i-cur)mxto(dp[i-cur+v],dp[i+v]+(cost<<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; for(int i=0;i<n;++i){  if(tot>=l){   if(up[i]<=0)take[i]=up[i];   else take[i]=min(a[i],(l-cur)/up[i]);  }  else{   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-v<=cur&&cur<=l+v); 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]==-LINF)pf("impossible\n"); else pf("%lld\n",dp[v]);}
      |                                                                                 ^
vault.cpp:1:10: fatal error: bits/stdc++.h>usin: No such file or directory
    1 | #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 1000000007inline 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 200005int 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)iter=2;  num=(num-1)/2;  if(val>=0){   for(int i=v;i>=-v;--i){    int cur=val<<cnt;    if(i+cur<=v)mxto(dp[i+cur+v],dp[i+v]+(cost<<cnt));   }  }  else{   for(int i=-v;i<=v;++i){    int cur=val<<cnt;    if(-v<=i-cur)mxto(dp[i-cur+v],dp[i+v]+(cost<<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; for(int i=0;i<n;++i){  if(tot>=l){   if(up[i]<=0)take[i]=up[i];   else take[i]=min(a[i],(l-cur)/up[i]);  }  else{   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-v<=cur&&cur<=l+v); 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]==-LINF)pf("impossible\n"); else pf("%lld\n",dp[v]);}
      |          ^~~~~~~~~~~~~~~~~~~~
compilation terminated.