QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404055#6298. ColoringWZKQWQWA 14ms39600kbC++141.8kb2024-05-03 10:21:052024-05-03 10:21:05

Judging History

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

  • [2024-05-03 10:21:05]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:39600kb
  • [2024-05-03 10:21:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
typedef long long ll;
int n,s,w[N],p[N],a[N],o[N],v[N],cnt;
ll f[N][N];
vector<int>e[N];
void dfs(int x){
	for(int i = 0;i <= n;++i) f[x][i] = ((i & 1)?w[x]:0) - (ll)p[x] * i;
	for(int to:e[x]){
		if(v[to]) continue;
		dfs(to);
		ll tmp = f[to][0];
		for(int i = 1;i <= n;++i){
			tmp = max(tmp,f[to][i]);
			f[x][i] += tmp;
		}
	}
}
int main(){
	//freopen("cheese.in","r",stdin);
	//freopen("cheese.out","w",stdout);
	cin >> n >> s;
	for(int i = 1;i <= n;++i) cin >> w[i];
	for(int i = 1;i <= n;++i) cin >> p[i];
	for(int i = 1;i <= n;++i){
		cin >> a[i];
		e[a[i]].push_back(i);
	} 
	int tmp = s;
	for(int i = 1;i <= n;++i){
		o[++cnt] = tmp;
		tmp = a[tmp];
		if(tmp == s) break;
	}
	if(tmp == s){
		for(int i = 1;i <= cnt;++i) v[o[i]] = 1;
		for(int i = 1;i <= cnt;++i){
			
			dfs(o[i]);
			//cout << o[i] << ' ' << f[o[i]][0] << ' ' << f[o[i]][1] << ' ' << f[o[i]][2] << endl;
		} 
		if(cnt == 2){
			cout << max(f[s][1] + f[a[s]][0],max(f[s][1] + f[a[s]][1],f[s][2] + f[s][0])) + p[s] << endl;
			return 0;
		}
		for(int i = 2;i <= cnt;++i) if(i < cnt - i + 2) swap(o[i],o[cnt - i + 2]);
		ll ans = -1e18;
		for(int i = 0;i <= n - 2;++i){
			ll sum0 = 0,sum1 = 0,sum2 = 0,tmp = 0;
			for(int j = 1;j <= cnt;++j) sum0 += f[o[j]][i];
			//ll tmp = f[1][i + 2] - f[1][i + 1];
			//ll tmp1 = tmp;
			for(int j = 1;j <= cnt;++j){
				sum1 += f[o[j]][i + 1] - f[o[j]][i],sum2 += f[o[j]][i + 2] - f[o[j]][i + 1];
				tmp = max(tmp,sum2);
				ans = max(ans,sum0 + sum1 + tmp);
				//tmp += f[j][i ]
			}
		}
		cout << ans + p[s] << endl;
		
	} else {
		dfs(s);
		ll ans = f[s][1];
		for(int i = 1;i <= n;++i) ans = max(ans,f[s][i]);
		cout << ans + p[s] << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3716kb

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

10 8
36175808 53666444 14885614 -14507677 -92588511 52375931 -87106420 -7180697 -158326918 98234152
17550389 45695943 55459378 18577244 93218347 64719200 84319188 34410268 20911746 49221094
8 1 2 2 8 8 4 7 8 4

output:

35343360

result:

ok 1 number(s): "35343360"

Test #3:

score: -100
Wrong Answer
time: 14ms
memory: 39600kb

input:

5000 1451
531302480 400140870 -664321146 -376787089 -440627168 -672055995 924309614 2764785 -225700856 880835131 -435550509 162278080 -635253658 251803267 -499868931 213283508 603121701 -603347266 541062018 -502078443 -585620031 486788884 864390909 -670529282 -63580194 512939729 691685896 481123612 ...

output:

115410120911

result:

wrong answer 1st numbers differ - expected: '83045140866', found: '115410120911'