QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404055 | #6298. Coloring | WZKQWQ | WA | 14ms | 39600kb | C++14 | 1.8kb | 2024-05-03 10:21:05 | 2024-05-03 10:21:05 |
Judging History
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;
}
詳細信息
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'