QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377266#6194. Knapsack ProblemCryingTL 45ms4680kbC++141.5kb2024-04-05 10:11:352024-04-05 10:11:36

Judging History

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

  • [2024-04-05 10:11:36]
  • 评测
  • 测评结果:TL
  • 用时:45ms
  • 内存:4680kb
  • [2024-04-05 10:11:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std; typedef long long ll;
const ll INF = 1e18,M = 30;
void tomax(ll& x,ll y){x = (x>y)?(x):(y);}

int T,k,c[16],a[4];

ll dp[M+1][4096],g[16][625],pw[5];

void solve(){
	pw[0] = 1,pw[1] = 5,pw[2] = 25,pw[3] = 125,pw[4] = 625;

	cin>>k;
	for(int i=1;i<(1<<k);i++)cin>>c[i]; for(int i=0;i<k;i++)cin>>a[i];

	for(int i=0;i<(1<<k);i++)for(int S=0;S<pw[k];S++)g[i][S] = -INF;
	for(int S=0;S<(1<<(1<<k));S++)if(!(S&1)){
		int lim = 0,nxt = 0;
		for(int j=0;j<k;j++){
			int cnt = 0;
			for(int p=1;p<(1<<k);p++)if( (S>>p&1) && (p>>j&1) ){
				lim ^= 1<<j;
				cnt++;
			}
			nxt += (cnt>>1) * pw[j];
		}
		ll sum = 0;
		for(int p=1;p<(1<<k);p++)if(S>>p&1)sum += c[p];
		tomax(g[lim][nxt],sum);
	}

	for(int i=0;i<=M;i++)for(int S=0;S<(1<<3*k);S++)dp[i][S] = -INF;
	dp[0][0] = 0;

	for(int i=0;i<M;i++){
		ll pv,qv;
		for(int S=0;S<(1<<3*k);S++)if((pv=dp[i][S]) != -INF){
			int lim = 0;
			for(int j=0,p=7;j<k;j++,p<<=3){
				int val = ((S&p)>>3*j)&1;
				lim |= (val != (a[j]>>i&1)) << j;
			}
			
			for(int T=0;T<pw[k];T++)if((qv=g[lim][T]) != -INF){
				int nxt = 0;
				for(int j=0,p=7;j<k;j++,p<<=3){
					int val = (((S&p)>>3*j)+(lim>>j&1))/2 + (T/pw[j]%5);
					assert(val <= 7);
					nxt |= val << (3*j);
				}
				tomax(dp[i+1][nxt],pv + (qv << i));
			}
			
		}
	}

	ll ans = dp[M][0];
	(ans == -INF) ? (cout<<"-1\n") : (cout<<ans<<"\n");
}

int main(){
	cin>>T;
	while(T--)solve();

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 45ms
memory: 4680kb

input:

3
2
1 2 4
4 5
3
3226252 19270256 2430652 1187613 12496062 10286165 17494834
24 85 34
4
901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555
529321239 218214127 92942310 207467810

output:

18
1949753378
7832404777567179

result:

ok 3 number(s): "18 1949753378 7832404777567179"

Test #2:

score: -100
Time Limit Exceeded

input:

100
4
4488409 9842893 14331290 11289097 15777479 21131954 25620334 6146092 10634508 15988956 20477387 17435190 21923584 27278027 31766493
200477197 258791439 590664017 982949628
4
5484152 19851747 25335961 6555937 12039831 26407861 31891996 10897184 16381166 30749333 36233145 17453055 22937114 37304...

output:

16156444320083421
24565535429631234
29418802996321901
30685727712782520
21026118053726857
27272339796311010
28831028447377015
34577176834491128
9058894962996375
21525085254465501
6657186892229297
16750628911275484
11217846865301187
12674726744043780
33873234230125448
3890237279573366
319038768614465...

result: