QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#297 | #72125 | #5359. 面国建设 | Crysfly | Crysfly | Failed. | 2023-01-14 09:34:35 | 2023-01-14 09:34:36 |
Details
Extra Test:
Accepted
time: 3ms
memory: 7380kb
input:
114 514
output:
11321
result:
ok single line: '11321'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72125 | #5359. 面国建设 | Crysfly | 100 ✓ | 159ms | 9776kb | C++17 | 1.2kb | 2023-01-14 09:34:17 | 2023-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;
}