QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326707#8225. 最小值之和linrui0 2ms8724kbC++142.6kb2024-02-13 19:31:242024-02-13 19:31:24

Judging History

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

  • [2024-02-13 19:31:24]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:8724kb
  • [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%