QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149619#5480. New Year FestivallgvcRE 39ms379928kbC++233.4kb2023-08-24 23:00:372023-08-24 23:00:38

Judging History

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

  • [2023-08-24 23:00:38]
  • 评测
  • 测评结果:RE
  • 用时:39ms
  • 内存:379928kb
  • [2023-08-24 23:00:37]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define eps 0.00000001
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void){
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w*x;
}
void write(int x){
	static int sta[20];
	int top=0;
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x){
	write(x);
	pc('\n');
}
struct n_t{
	int x,y;
};
inline bool cmp(n_t m,n_t n) {
	return m.x<n.x;
}
int N,s[15],l[15],f[15],p[15],q[15],x[15][70],y[15][70],vi[16000009],as=INF_LL;
std::vector<n_t> dp,dq,stt[16000009];
inline int qr(int x) {
	if(x>dq[dq.size()-1].x) return dq[dq.size()-1].y;
	if(dq.size()==1) return dq[0].y;
	int l=0,r=dq.size()-2,md;
	while(l<r) {
		md=(l+r+1)>>1;
		if(x>=dq[md].x) l=md;else r=md-1;
	}
	return dq[l].y+(dq[l+1].y-dq[l].y)/(dq[l+1].x-dq[l].x)*(x-dq[l].x);
}
std::vector<n_t> ff(int xx) {
	dp.clear();
	dq.clear();
	dp.push_back((n_t){0,0});
	dp.push_back((n_t){100000000,0});
	int vq=0;
	for(int i=1;i<=xx;i++) {
		vq=vq*N+f[i];
		if(i<=7&&vi[vq]) {
			dp=stt[vq];
			if(dp.empty()) return dp;
			continue;
		}
		dq=dp;
		for(int j=1;j<=s[f[i]];j++) {
			if(x[f[i]][j]>=dq[0].x) dp.push_back((n_t){x[f[i]][j],qr(x[f[i]][j])});
		}
		dq.clear();
		std::sort(dp.begin(),dp.end(),cmp);
		for(int j=0;j<dp.size();j++) if(dp[j].x<=x[f[i]][s[f[i]]]&&dp[j].x>=x[f[i]][1]) dq.push_back(dp[j]);
		int st=1;
		for(int j=0;j<dq.size();j++) {
			while(st+1<s[f[i]]&&dq[j].x>=x[f[i]][st+1]) st++;
			if(s[f[i]]==1) dq[j].y+=y[f[i]][1];
			else dq[j].y+=y[f[i]][st]+(y[f[i]][st+1]-y[f[i]][st])/(x[f[i]][st+1]-x[f[i]][st])*(dq[j].x-x[f[i]][st]);
			dq[j].x+=l[f[i]];
		}
		if(dq.empty()) {
			if(i<=6) vi[vq]=1;
			return dq;
		}
		dp.clear();
		dp.push_back(dq[0]);
		for(int j=1;j<dq.size();j++) {
			if(dq[j].x!=dq[j-1].x) dp.push_back(dq[j]);
		}
		for(int j=1;j<dp.size();j++) {
			dp[j].y=std::min(dp[j].y,dp[j-1].y);
		}
		if(i<=7) {
			vi[vq]=1;
			stt[vq]=dp;
		}
	}	
	return dp;
}
inline void tryy(int x) {
	int k=0,ct=1;
	for(int i=1;i<=N;i++) if((x>>i-1)&1) p[++k]=i,q[k]=k-1;
	for(int i=1;i<=k;i++) ct=ct*i;
	while(ct--) {
		for(int i=1;i<=k;i++) f[i]=p[q[i]+1];
		dq=ff(k);
		if(!dq.empty()) as=std::min(as,dq[dq.size()-1].y);
		std::next_permutation(q+1,q+k+1);
	}
}
signed main(void) {
    //freopen("m.in","r",stdin);
    //freopen("m.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++) {
		s[i]=read();l[i]=read();
		for(int j=1;j<=s[i];j++) {
			x[i][j]=read();
			y[i][j]=read();
		}
	}
	srand(time(NULL));
	tryy((1<<N)-1);
	printf("%lld\n",as);
/*	int s=N/2;
	for(int i=0;i<(1<<N);i++) {
		if(__builtin_popcount(i)!=s) continue;
		tryy(i);
	}
	if(N%2==1) {
		for(int i=0;i<(1<<N);i++) {
			if(__builtin_popcount(i)!=s+1) continue;
			tryy(i);
		}		
	}*/
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 39ms
memory: 379928kb

input:

3
3 50
300 2500
350 0
400 3000
2 120
380 0
400 2400
4 160
0 800
400 0
450 100
950 4600

output:

1460

result:

ok single line: '1460'

Test #2:

score: 0
Accepted
time: 32ms
memory: 379904kb

input:

4
2 160
384 0
1000 2464
3 280
0 2646
441 0
1000 2795
1 160
544 0
2 240
720 0
1220 2000

output:

2022

result:

ok single line: '2022'

Test #3:

score: -100
Runtime Error

input:

11
6 192168
0 8547618
626988 33627138
706274 36560720
1103426 50858192
1399013 55291997
1418093 55559117
6 161415
0 58611901
321482 57647455
349707 57534555
550744 55524185
885629 50500910
1448846 27972230
6 195811
0 6825079
56106 8339941
78686 8836701
323216 12993711
525834 15627745
1414450 2095944...

output:


result: