QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326674 | #6298. Coloring | C1942huangjiaxu | WA | 43ms | 199768kb | C++14 | 846b | 2024-02-13 18:18:21 | 2024-02-13 18:18:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
vector<int>e[N];
int n,s,a[N],w[N],p[N],rg[N],cr,c[N];
ll f[N][N],ans,sum;
bool vis[N];
void dfs(int x){
for(int i=1;i<n;++i)f[x][i]=-1ll*p[x]*i+(i&1)*w[x];
for(auto v:e[x])if(!vis[v]){
dfs(v);
ll mx=0;
for(int j=1;j<n;++j){
mx=max(mx,f[v][j]);
f[x][j]+=mx;
}
}
}
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;++i)scanf("%d",&w[i]);
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
e[a[i]].push_back(i);
}
for(int i=s;!vis[i];i=a[i])vis[i]=true,rg[++cr]=i;
for(int i=1;i<=cr;++i)dfs(rg[i]);
for(int i=1;c[s]<n;--i){
if(!i)i=cr;
int x=rg[i];
sum-=f[x][c[x]];
++c[x];
sum+=f[x][c[x]];
ans=max(ans,sum+p[s]);
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4028kb
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: 3968kb
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: 43ms
memory: 199768kb
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:
599586694040
result:
wrong answer 1st numbers differ - expected: '83045140866', found: '599586694040'