QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404153#6298. Coloring275307894aWA 12ms109024kbC++142.2kb2024-05-03 14:02:442024-05-03 14:02:45

Judging History

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

  • [2024-05-03 14:02:45]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:109024kb
  • [2024-05-03 14:02:44]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5000+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const ll INF=1e18+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int vis[N],n,s,w[N],p[N],A[N];vector<int> S[N];
ll dp[N][N];
void DP(int x){
	for(int i=0;i<=n+2;i+=2) dp[x][i]=1ll*-p[x]*i;
	for(int i=1;i<=n+2;i+=2) dp[x][i]=1ll*-p[x]*i+w[x];
	for(int i:S[x]) if(!vis[i]){
		DP(i);
		ll mx=-INF;
		for(int j=0;j<=n+2;j++){
			mx=max(mx,dp[i][j]);
			dp[x][j]+=mx;
		}
	}
}
int B[N],Bh;
ll f[N][3];
void Solve(){
	int i,j;scanf("%d%d",&n,&s);
	for(i=1;i<=n;i++) scanf("%d",&w[i]);
	for(i=1;i<=n;i++) scanf("%d",&p[i]);
	for(i=1;i<=n;i++) scanf("%d",&A[i]),S[A[i]].emplace_back(i);
	int x=s;while(!vis[x]) vis[x]=1,x=A[x];
	if(x^s){
		DP(s);
		printf("%lld\n",max(dp[s][1],dp[s][2])+p[s]);
		return;
	}
	if(A[A[s]]==s){
		DP(s);
		printf("%lld\n",max({dp[s][1],dp[s][2],dp[s][1]+dp[A[s]][1]})+p[s]);
		return;
	}
	B[Bh=1]=s;x=A[s];while(x^s) B[++Bh]=x,x=A[x];
	reverse(B+2,B+Bh+1);
	for(i=1;i<=Bh;i++) DP(B[i]);
	ll ans=-INF;
	for(i=0;i<=n;i++){
		Me(f,0x3f);Me(f[Bh+1],0);
		for(j=Bh;j;j--){
			ll mx=-INF;
			for(int x:{0,1,2}){
				mx=max(mx,f[j+1][x]);
				f[j][x]=mx+dp[B[j]][i+x];
			}
		}
		ans=max({ans,i?f[1][0]:-INF,f[1][1],f[1][2]});
	}
	printf("%lld\n",ans+p[s]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 0
Accepted
time: 3ms
memory: 34808kb

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:

83045140866

result:

ok 1 number(s): "83045140866"

Test #4:

score: -100
Wrong Answer
time: 12ms
memory: 109024kb

input:

5000 325
790437050 -881570876 262369906 -462921420 -706598183 -486649546 -226864203 505745549 30451944 124046215 968419787 -21612898 145640891 11293206 830678227 214238313 -277762746 363570356 -123386912 -428728586 -928118626 44181027 -201770288 -776436064 -758985629 -330862963 -543373739 -904928126...

output:

313292164097

result:

wrong answer 1st numbers differ - expected: '484763000532', found: '313292164097'