QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709110 | #8225. 最小值之和 | miaomiaomiaowu | 0 | 2ms | 11896kb | C++20 | 4.6kb | 2024-11-04 11:36:10 | 2024-11-04 11:36:10 |
Judging History
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%