QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326707 | #8225. 最小值之和 | linrui | 0 | 2ms | 8724kb | C++14 | 2.6kb | 2024-02-13 19:31:24 | 2024-02-13 19:31:24 |
answer
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using u64=unsigned long long;
using LF=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define CT const&
#define IL inline
#define PB push_back
template<class T>
IL void tomn(T &x,T CT y){y<x?x=y,0:0;}
template<class T>
IL void tomx(T &x,T CT y){x<y?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
const LF EPS=1e-10L;
IL int dcmp(LF x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const LL INF=4e18L;
const int N=85;
void exgcd(int a,int b,int &x,int &y,int &g){
if(!b)return x=1,y=0,g=a,void();
exgcd(b,a%b,y,x,g),y-=(a/b)*x;
}
IL int mod(int x,int y){return x%=y,x+(x<0)*y;}
IL int dv(int x,int y){return (x-mod(x,y))/y;}
struct D{int x,m;}f[N][N][N];
bool operator<(D x,D y){return x.x<y.x;}
int n,g[N],ans[N];
void dfs(int l,int r,int x){
if(l==r)return;
D d=f[l][r][x%(r-l)];
F(i,l,r-1)ans[i]+=(d.x-x)/(r-l);
dfs(l,d.m,d.x),dfs(d.m+1,r,d.x);
}
IL bool ck(int l,int r,int x){return x<=f[l][r][x%(r-l)].x;}
IL void to(int l,int r,D x){tomx(f[l][r][x.x%(r-l)],x);}
int main(){
#ifdef LOCAL
freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
#endif
scanf("%d",&n);
if(n==1)puts("Yes"),exit(0);
F(i,1,n)scanf("%d",g+i);
F(i,0,N-1)F(j,0,N-1)F(k,0,N-1)f[i][j][k]=D{-1};
G(l,n,1)F(r,l,n){
if(l==r){
f[l][l][0]=D{g[l]};
continue;
}if(l==r-1){
if(g[l]==g[r])tomx(f[l][r][0],D{g[l],l});
continue;
}
F(m,l,r-1){
if(m==l){
if(ck(l+1,r,g[l]))to(l,r,D{g[l],m});
continue;
}if(m==r-1){
if(ck(l,r-1,g[r]))to(l,r,D{g[r],m});
continue;
}int p=m-l,q=r-m-1,x,y,g,L,M=r-l;
exgcd(p,q,x,y,g),L=p/g*q,M/=__gcd(L,M);
// int mn1=max(dv(-x*g+q-1,q),dv(y*g+p-1,p));
// int mn2=max(dv(x*g+q-1,q),dv(-y*g+p-1,p));
F(i,0,L-1){
int j=i%p,k=i%q,a=f[l][m][j].x,b=f[m+1][r][k].x;
if(a<0||b<0)continue;
int x2=(a-b)/g*x,y2=(b-a)/g*y,X=max(dv(-x2*g+q-1,q),dv(-y2*g+p-1,p));
int c=a-p*(x2+q/g*X);
{
// cerr<<x2<<" "<<y2<<endl;
// int x2=x,y2=y;
// x2*=(a-b)/g,y2*=-(a-b)/g;
// cerr<<a-x2*p<<" "<<b-y2*q<<endl;
// x2+=q/g*X,y2+=p/g*X;
// cerr<<x2<<" "<<y2<<endl;
// cerr<<a-x2*p<<" "<<b-y2*q<<endl;
}
// int c=a-p/g*(a-b)*(x+q/g*(a>=b?mn1:-mn2));
// cerr<<a<<" "<<p<<" "<<b<<" "<<q<<" "<<c<<endl;
F(j,0,M-1){
if(c<0)break;
to(l,r,D{c,m}),c-=L;
}
}
}
}if(!ck(1,n,0))puts("No"),exit(0);
puts("Yes"),dfs(1,n,0);
F(i,1,n-1)printf("%d ",ans[i]);
}
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: 8720kb
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: 8596kb
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: 0ms
memory: 8724kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 2ms
memory: 8680kb
input:
5 11 11 10 5 5
output:
Yes 5 4 1 2
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 1ms
memory: 8604kb
input:
5 10 10 10 4 4
output:
Yes 4 4 1 1
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 0ms
memory: 8720kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 2ms
memory: 8580kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 0ms
memory: 8652kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 1ms
memory: 8576kb
input:
5 10 10 8 5 5
output:
Yes 5 3 1 2
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 1ms
memory: 8720kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 8588kb
input:
5 5 5 22 31 31
output:
Yes 2 1 10 19
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 0ms
memory: 8544kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 0ms
memory: 8536kb
input:
5 16 16 4 12 12
output:
Yes 13 1 1 9
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 2ms
memory: 8668kb
input:
5 29 29 24 26 26
output:
Yes 11 6 6 8
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 2ms
memory: 8588kb
input:
5 0 33 33 32 32
output:
Yes 0 13 10 12
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 0ms
memory: 8596kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 8596kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 2ms
memory: 8548kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 1ms
memory: 8596kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 2ms
memory: 8496kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 2ms
memory: 8480kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 2ms
memory: 8532kb
input:
5 6 7 7 6 6
output:
Yes 2 3 1 3
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 2ms
memory: 8720kb
input:
5 25 25 24 20 20
output:
Yes 8 7 5 5
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 0ms
memory: 8400kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 2ms
memory: 8532kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 8392kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 2ms
memory: 8480kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 0ms
memory: 8608kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 2ms
memory: 8352kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 8596kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 2ms
memory: 8548kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 2ms
memory: 8656kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: -11
Wrong Answer
time: 0ms
memory: 3684kb
input:
1 233
output:
Yes
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%