QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226189 | #6298. Coloring | ucup-team1198# | WA | 75ms | 427952kb | C++20 | 2.3kb | 2023-10-25 17:58:10 | 2023-10-25 17:58:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int MAXN = 5050;
vector<int> G[MAXN];
int n;
int A[MAXN];
long long w[MAXN];
long long p[MAXN];
long long dp[MAXN][MAXN];
long long pref_mx[MAXN][MAXN];
void dfs(int v) {
for (int k = 0; k <= n; ++k) {
dp[v][k] = k % 2 ? w[v] : 0;
}
for (int u : G[v]) {
dfs(u);
for (int k = 0; k <= n; ++k)
dp[v][k] += pref_mx[u][k];
}
pref_mx[v][0] = dp[v][0];
for (int k = 1; k <= n; ++k)
pref_mx[v][k] = max(pref_mx[v][k - 1], dp[v][k] - p[v] * 1ll * k);
}
long long pref_sum[MAXN][MAXN];
const long long INF = 1e18;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int s;
cin >> n >> s;
--s;
for (int i = 0; i < n; ++i)
cin >> w[i];
for (int i = 0; i < n; ++i)
cin >> p[i];
for (int i = 0; i < n; ++i) {
cin >> A[i];
--A[i];
}
vector<bool> used(n, false);
vector<int> cycle;
int cur = s;
while (!used[cur]) {
used[cur] = true;
cycle.emplace_back(cur);
cur = A[cur];
}
for (int i = 0; i < n; ++i) {
if (!used[i])
G[A[i]].emplace_back(i);
}
if (cur != s) {
// no cycle, just s
dfs(s);
cout << max(dp[s][1], dp[s][2] - p[s]) << '\n';
} else {
// have a cycle
reverse(cycle.begin() + 1, cycle.end());
for (int j = 0; j < cycle.size(); ++j)
dfs(cycle[j]);
for (int k = 0; k <= n; ++k) {
pref_sum[k][0] = 0;
for (int j = 0; j < cycle.size(); ++j)
pref_sum[k][j + 1] = pref_sum[k][j] + dp[cycle[j]][k] - p[cycle[j]] * k;
}
long long ans = -INF;
for (int k = 1; k + 1 <= n; k += 2) {
long long l_mx = pref_sum[k + 1][0] - pref_sum[k][0];
for (int r = 1; r <= cycle.size(); ++r) {
l_mx = max(l_mx, pref_sum[k + 1][r] - pref_sum[k][r]);
long long cur_r = pref_sum[k][r] - pref_sum[k - 1][r];
ans = max(ans, l_mx + cur_r + pref_sum[k - 1][cycle.size()]);
}
}
cout << ans + p[s] << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9956kb
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: 9808kb
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: 12ms
memory: 217628kb
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: 75ms
memory: 427952kb
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'