QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300270#6298. ColoringcqbzlyWA 255ms786844kbC++141.6kb2024-01-07 22:17:252024-01-07 22:17:25

Judging History

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

  • [2024-01-07 22:17:25]
  • 评测
  • 测评结果:WA
  • 用时:255ms
  • 内存:786844kb
  • [2024-01-07 22:17:25]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
int n,s,a[N],vs[N];
ll f[N][N][4],w[N],p[N];
vector<int>G[N];
void dfs(int u){
    vs[u]=1;
    for(auto v:G[u])if(!vs[v])dfs(v);
}
void dfs0(int u){
    if(u!=s){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=3;j++){
                f[u][i][j]=-i*p[u]+(i&1)*w[u];
            }
        }
    }
    for(auto v:G[u]){
        if(v==s)continue;
        dfs0(v);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=3;j++){
                f[u][i][j]+=f[v][i][j];
                //djnb
                f[u][i][j]=max(f[u][i][j],(ll)-inf);
            }
        }
    }
    if(u==a[s])for(int i=0;i<=n;i++)f[u][i][3]=-inf;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=3;j++){
            f[u][i][j]=max(f[u][i][j],f[u][i-1][min(j+1,3)]);
        }
    }
    for(int i=1;i<=n;i++)for(int j=0;j<=3;j++)f[u][i][j]=max(f[u][i][j],(ll)-inf);
}
signed main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    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],G[a[i]].pb(i);
    dfs(s);memset(f,-0x3f,sizeof f);
    if(!vs[a[s]]){
        for(int i=1;i<=2;i++)f[s][i][0]=-(i-1)*p[s]+(i&1)*w[s];
    }
    else{
        for(int i=1;i<=n;i++)f[s][i][0]=-(i-1)*p[s]+(i&1)*w[s];
    }
    dfs0(s);
    ll res=-inf;
    for(int i=0;i<=n;i++)res=max(res,f[s][i][0]);
    cout<<res;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 786464kb

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: 28ms
memory: 786516kb

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: 51ms
memory: 786812kb

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: 255ms
memory: 786844kb

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:

692335671638

result:

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