QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326531#8225. 最小值之和NATURAL60 2ms7980kbC++142.9kb2024-02-13 13:00:522024-02-13 13:00:53

Judging History

你现在查看的是最新测评结果

  • [2024-02-13 13:00:53]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:7980kb
  • [2024-02-13 13:00:52]
  • 提交

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%