QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709110#8225. 最小值之和miaomiaomiaowu0 2ms11896kbC++204.6kb2024-11-04 11:36:102024-11-04 11:36:10

Judging History

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

  • [2024-11-04 11:36:10]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:11896kb
  • [2024-11-04 11:36:10]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<ll,ll>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
    char c;x=0;bool f=0;
    for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
struct fastmod{
    typedef unsigned long long u64;
    typedef __uint128_t u128;
    int m;u64 b;
    fastmod(int m):m(m),b(((u128)1<<64)/m){}
    int reduce(u64 a){
        u64 q=((u128)a*b)>>64;
        int r=a-q*m;
        return r<m?r:r-m;
    }
}z(2);
int n,Lx[81],Rx[81];
ll a[81],dp[81][81][81],LCM[81][81],dis[81],mn[81][81],ans[81];
struct Node{int k,l,r;ll x;}pd[81][81][81];
inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll x0=x,y0=y;x=y0,y=x0-a/b*y0;
    return d;
}
inline pii calc(ll t1,ll m1,ll lim1,ll t2,ll m2,ll lim2){
    if(m2<m1)swap(t1,t2),swap(m1,m2),swap(lim1,lim2);
    ll X,Y,d=exgcd(t1,t2,X,Y),xx=m2-m1;
    if(xx%d!=0)return MP(-1,-1);
    X*=xx/d,Y*=xx/d,Y=-Y;
    ll mx=0,q1=LCM[t1][t2]/t1,q2=LCM[t1][t2]/t2;
    if(X>lim1)mx=max(mx,(X-lim1-1)/q1+1);
    if(Y>lim2)mx=max(mx,(Y-lim2-1)/q2+1);
    if(mx!=0)X-=q1*mx,Y-=q2*mx;
    ll mn;
    if(X==lim1||Y==lim2)mn=0;
    else mn=min((lim1-X)/q1,(lim2-Y)/q2);
    if(mn!=0)X+=mn*q1,Y+=mn*q2;
    if(X<0||Y<0)return MP(-1,-1);
    return MP(X*t1+m1,min(X/q1,Y/q2));
}
inline void getans(int l,int r,int x,ll nw){
    if(l==r)return;
    int k=pd[l][r][x].k,xl=pd[l][r][x].l,xr=pd[l][r][x].r;
    ll num=(pd[l][r][x].x-nw)/(r-l);
    for(int i=l;i<r;i++)ans[i]+=num;
    getans(l,k,xl,pd[l][r][x].x);
    getans(k+1,r,xr,pd[l][r][x].x);
}
int main(){
    for(int i=1;i<=80;i++)for(int j=1;j<=80;j++)
        LCM[i][j]=i/__gcd(i,j)*j;
    in(n);
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=n;i++)in(a[i]);
    for(int i=1;i<n;i++)if(a[i]==a[i+1])dp[i][i+1][0]=a[i],pd[i][i+1][0]=Node{i,0,0,a[i]};
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){
        mn[i][j]=a[i];
        for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],a[k]);
    }
    for(int d=3;d<=n;d++){
        for(int l=1,r=d;r<=n;l++,r++){
            for(int k=l;k<r;k++){
                memset(dis,-1,sizeof dis);
                if(k==l){
                    for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
                        ll num=(r-k-1)*dp[k+1][r][xr]+xr;
                        if(num>=a[l]&&(num-a[l])%(r-k-1)==0){
                            int rst=a[l]%(r-l);ll qwq=a[l]/(r-l);
                            if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,0,xr,a[l]};
                        }
                    }
                    continue;
                }
                if(k==r-1){
                    for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
                        ll num=(k-l)*dp[l][k][xl]+xl;
                        if(num>=a[r]&&(num-a[r])%(k-l)==0){
                            int rst=a[r]%(r-l);ll qwq=a[r]/(r-l);
                            if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,xl,0,a[r]};
                        }
                    }
                    continue;
                }
                for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
                    for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
                        pii qwq=calc(k-l,xl,dp[l][k][xl],r-k-1,xr,dp[k+1][r][xr]);
                        if(qwq.first==-1)continue;
                        int t=LCM[r-k-1][k-l];
                        while(qwq.second>=0){
                            ll xx=qwq.first%(r-l),yy=qwq.first/(r-l);
                            if(yy>dis[xx])dis[xx]=yy,Lx[xx]=xl,Rx[xx]=xr;
                            qwq.second--,qwq.first-=t;
                        }
                    }
                }
                for(int i=0;i<r-l;i++)if(dis[i]!=-1){
                    if(dis[i]>dp[l][r][i]){
                        dp[l][r][i]=dis[i],pd[l][r][i]=Node{k,Lx[i],Rx[i],dis[i]*(r-l)+i};
                    }
                }
            }
        }
    }
    if(dp[1][n][0]==-1)return puts("No"),0;
    getans(1,n,0,0);
    for(int i=1;i<n;i++)for(int j=i;j<n;j++){
        mn[i][j]=ans[i];
        for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],ans[k]);
    }
    for(int i=1;i<=n;i++){
        ll qwq=0;
        for(int j=1;j<i;j++)qwq+=mn[j][i-1];
        for(int j=i;j<n;j++)qwq+=mn[i][j];
        if(qwq!=a[i])return puts("No"),0;
    }
    puts("Yes");
    for(int i=1;i<n;i++)cout<<ans[i]<<' ';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 2ms
memory: 9076kb

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4 

result:

ok The answer is correct.

Test #2:

score: 11
Accepted
time: 0ms
memory: 9120kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1 

result:

ok The answer is correct.

Test #3:

score: 11
Accepted
time: 2ms
memory: 11896kb

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4 

result:

ok The answer is correct.

Test #4:

score: 11
Accepted
time: 1ms
memory: 8332kb

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2 

result:

ok The answer is correct.

Test #5:

score: 11
Accepted
time: 0ms
memory: 8396kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1 

result:

ok The answer is correct.

Test #6:

score: 11
Accepted
time: 0ms
memory: 9628kb

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1 

result:

ok The answer is correct.

Test #7:

score: 11
Accepted
time: 1ms
memory: 8784kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

score: 11
Accepted
time: 1ms
memory: 8404kb

input:

5
2 2 6 11 11

output:

Yes
2 0 3 8 

result:

ok The answer is correct.

Test #9:

score: 11
Accepted
time: 1ms
memory: 9016kb

input:

5
10 10 8 5 5

output:

Yes
5 3 1 2 

result:

ok The answer is correct.

Test #10:

score: 11
Accepted
time: 0ms
memory: 9576kb

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7 

result:

ok The answer is correct.

Test #11:

score: 11
Accepted
time: 1ms
memory: 8888kb

input:

5
5 5 22 31 31

output:

Yes
2 1 10 19 

result:

ok The answer is correct.

Test #12:

score: 11
Accepted
time: 1ms
memory: 9140kb

input:

5
8 33 38 38 29

output:

Yes
2 11 16 9 

result:

ok The answer is correct.

Test #13:

score: 11
Accepted
time: 0ms
memory: 9112kb

input:

5
16 16 4 12 12

output:

Yes
13 1 1 9 

result:

ok The answer is correct.

Test #14:

score: 11
Accepted
time: 1ms
memory: 8264kb

input:

5
29 29 24 26 26

output:

Yes
11 6 6 8 

result:

ok The answer is correct.

Test #15:

score: 11
Accepted
time: 1ms
memory: 10020kb

input:

5
0 33 33 32 32

output:

Yes
0 13 10 12 

result:

ok The answer is correct.

Test #16:

score: 11
Accepted
time: 1ms
memory: 8312kb

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

score: 11
Accepted
time: 0ms
memory: 9272kb

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

score: 11
Accepted
time: 0ms
memory: 8792kb

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

score: 11
Accepted
time: 0ms
memory: 8836kb

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

score: 11
Accepted
time: 1ms
memory: 9044kb

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

score: 11
Accepted
time: 1ms
memory: 9424kb

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

score: 11
Accepted
time: 0ms
memory: 8096kb

input:

5
6 7 7 6 6

output:

Yes
2 3 1 3 

result:

ok The answer is correct.

Test #23:

score: 11
Accepted
time: 0ms
memory: 10048kb

input:

5
25 25 24 20 20

output:

Yes
8 7 5 5 

result:

ok The answer is correct.

Test #24:

score: 11
Accepted
time: 1ms
memory: 9252kb

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

score: 11
Accepted
time: 2ms
memory: 9424kb

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

score: 11
Accepted
time: 1ms
memory: 9116kb

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

score: 11
Accepted
time: 1ms
memory: 9352kb

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

score: 11
Accepted
time: 0ms
memory: 9468kb

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

score: 11
Accepted
time: 1ms
memory: 8928kb

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

score: 11
Accepted
time: 1ms
memory: 9392kb

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

score: 11
Accepted
time: 1ms
memory: 9408kb

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

score: 11
Accepted
time: 1ms
memory: 9576kb

input:

2
2 2

output:

Yes
2 

result:

ok The answer is correct.

Test #33:

score: 0
Wrong Answer
time: 1ms
memory: 8772kb

input:

1
0

output:

No

result:

wrong answer Line 1 expected 

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%