QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326531 | #8225. 最小值之和 | NATURAL6 | 0 | 2ms | 7980kb | C++14 | 2.9kb | 2024-02-13 13:00:52 | 2024-02-13 13:00:53 |
answer
#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
int a=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
return a*f;
}
int n,a[100],f[100],MID[81][81][81],dpl[81][81][81],dpr[81][81][81],dpm[81][81][81];
long long dp[81][81][81],X,Y,GCD,LCM;
inline int get_d(int l,int r)
{
if(l>r)return 0;
int mn=a[l];
for(int i=l;i<=r;++i)mn=min(mn,a[i]);
return mn;
}
inline int get_f(int p)
{
int ans=0;
for(int i=1;i<p;++i)ans+=get_d(i,p-1);
for(int i=p;i<n;++i)ans+=get_d(p,i);
return ans;
}
inline long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(!b)return x=1,y=0,a;
long long gcd=exgcd(b,a%b,y,x);
y-=a/b*x;
return gcd;
}
void solve(int l,int r,int v,long long delf,long long dela)
{
if(l==r)return;
if(r==l+1){return a[l]=f[l]-delf+dela,void();}
int lim=r-l;
if(f[l]%lim==v&&f[l]<=dp[l+1][r][f[l]%(lim-1)]&&f[l]==dp[l][r][v])
{
a[l]=(f[l]-delf)/lim+dela;
solve(l+1,r,f[l]%(lim-1),f[l],a[l]);
return;
}
if(f[r]%lim==v&&f[r]<=dp[l][r-1][f[r]%(lim-1)]&&f[r]==dp[l][r][v])
{
a[r-1]=(f[r]-delf)/lim+dela;
solve(l,r-1,f[r]%(lim-1),f[r],a[r-1]);
return;
}
a[MID[l][r][v]]=(dpm[l][r][v]-delf)/lim+dela;
solve(l,MID[l][r][v],dpl[l][r][v],dpm[l][r][v],a[MID[l][r][v]]);
solve(MID[l][r][v],r,dpr[l][r][v],dpm[l][r][v],a[MID[l][r][v]]);
return;
}
int main()
{
n=qread();
for(int i=1;i<=n;++i)f[i]=qread();
memset(dp,-1,sizeof(dp));
if(n==1)
{
if(f[1])puts("No");
else puts("Yes");
return 0;
}
for(int i=1;i<n;++i)if(f[i]==f[i+1])dp[i][i+1][0]=f[i];
for(int len=3,lim;len<=n;++len)for(int l=1,r;l+len-1<=n;++l)
{
r=l+len-1;lim=len-1;
for(int k=l,A,B;k<r;++k)
{
A=k-l,B=r-k-1;
if(!A){if(f[l]<=dp[k+1][r][f[l]%B])dp[l][r][f[l]%lim]=max(dp[l][r][f[l]%lim],1ll*f[l]);}
else if(!B){if(f[r]<=dp[l][k][f[r]%A])dp[l][r][f[r]%lim]=max(dp[l][r][f[r]%lim],1ll*f[r]);}
else
{
for(int i=0;i<A;++i)for(int j=0;j<B;++j)if(min(dp[l][k][i],dp[k+1][r][j])>=0)
{
GCD=exgcd(A,B,X,Y);
if((j-i)%GCD)continue;
X*=(j-i)/GCD;
X=i+X*A,LCM=1ll*A/GCD*B;
X=(X%LCM+LCM)%LCM;
Y=min(dp[l][k][i],dp[k+1][r][j]);
if(Y>=X)
{
Y=((Y-X)/LCM)*LCM+X;
for(int cnt=0,x;cnt<lim&&Y>=0;++cnt,Y-=LCM)if(Y>=dp[l][r][Y%lim])
{
x=Y%lim;
dp[l][r][x]=Y;
MID[l][r][x]=k;
dpl[l][r][x]=i;
dpr[l][r][x]=j;
dpm[l][r][x]=Y;
}
}
}
}
}
}
if(dp[1][n][0]<0)puts("No");
else
{
puts("Yes");
solve(1,n,0,0ll,0ll);
for(int i=1;i<n;++i)printf("%d ",a[i]);
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 11
Accepted
time: 0ms
memory: 7980kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 2ms
memory: 7928kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 2ms
memory: 7944kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: -11
Memory Limit Exceeded
input:
5 11 11 10 5 5
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%