QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#297#72125#5359. 面国建设CrysflyCrysflyFailed.2023-01-14 09:34:352023-01-14 09:34:36

Details

Extra Test:

Accepted
time: 3ms
memory: 7380kb

input:

114 514

output:

11321

result:

ok single line: '11321'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72125#5359. 面国建设Crysfly100 ✓159ms9776kbC++171.2kb2023-01-14 09:34:172023-01-14 09:34:20

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f3f3f3f3f

int s,c,V;
int f[maxn]; // min C of (2*S-C)
// add (i,j) : S+=i*j C+=i+j 2*S-C+=2*i*j-i-j

int mn[maxn];
void wk(int x){
	For(i,0,V)mn[i]=inf;
	int t=2*x*x-2*x;
	For(i,t,V){
		mn[i]=f[i-t]+x*2;
		if(i>=(2*x-1))mn[i]=min(mn[i],mn[i-(2*x-1)]+1);
		f[i]=min(f[i],mn[i]);
	}
}

signed main()
{
	s=read(),c=read()/2;
	memset(f,63,sizeof f);
	f[0]=0; V=2*s;
	for(int i=1;i*i<=s;++i)wk(i);
	int res=0;
	For(i,0,V){
		if(f[i]>c)continue;
	//	cout<<"i: "<<i<<" "<<f[i]<<endl;
		int nc=f[i],ns=(f[i]+i)/2;
		if(ns>s)continue;
	//	cout<<nc<<" "<<ns<<endl;
		int t=min((c-nc)/2,s-ns)+1;
		res+=t;
	}
	cout<<res-1;
	return 0;
}