QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326675#8225. 最小值之和linrui0 3ms8752kbC++142.7kb2024-02-13 18:22:552024-02-13 18:22:56

Judging History

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

  • [2024-02-13 18:22:56]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:8752kb
  • [2024-02-13 18:22:55]
  • 提交

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 c=a-p/g*(a-b)*(x+q/g*(a>=b?mn1:-mn2));
//				if(!ck(l,m,c)||!ck(m+1,r,c)){
//					cerr<<"!!! "<<p<<" "<<q<<" "<<g<<endl;
//					cerr<<x+mn1*q/g<<" "<<y-mn1*p/g<<endl;
//					cerr<<x-mn2*q/g<<" "<<y+mn2*p/g<<endl;
//					cerr<<-x*g<<" "<<q<<" "<<dv(-x*g+q-1,q)<<endl;
//					cerr<<x*g<<" "<<q<<" "<<dv(x*g+q-1,q)<<endl;
//					cerr<<-y*g<<" "<<p<<" "<<dv(-y*g+p-1,p)<<endl;
//					cerr<<y*g<<" "<<p<<" "<<dv(y*g+p-1,p)<<endl;
//					cerr<<"!!! "<<p<<" "<<q<<" "<<g<<endl
//					<<a<<" "<<x<<" "<<b<<" "<<y<<" "<<c<<endl;
//					cerr<<(x+q/g*(a>=b?mn1:-mn2))<<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: 8660kb

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: 8676kb

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: 8552kb

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
6 5 0 5 

result:

ok The answer is correct.

Test #5:

score: 0
Accepted
time: 3ms
memory: 8588kb

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: 8752kb

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: 8660kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

score: -11
Wrong Answer
time: 2ms
memory: 8624kb

input:

5
2 2 6 11 11

output:

No

result:

wrong answer Line 1 expected 0

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%