| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35914 |
2017-12-02T11:33:35 Z |
szawinis |
Chase (CEOI17_chase) |
C++14 |
|
329 ms |
333528 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+1, V = 102;
const ll INF = 1e17;
int n, lim, a[N];
ll ans, s[N], dp[N][V][2][2]; // vertex, cnt, dir = down, up, last
vector<int> g[N];
void dfs(int u, int p) {
// ll mx[V][2][2];
s[u] -= a[p];
dp[u][0][0][0] = 0;
dp[u][0][1][0] = 0;
// if(!p) dp[u][1][0][1] = mx[1][0][1] = s[u];
// dp[u][1][1][1] = mx[1][1][1] = s[u];
if(!p) dp[u][1][0][1] = s[u];
dp[u][1][1][1] = s[u];
ans = max(s[u] + a[p], ans);
// for(int x = 0; x <= lim; x++)
// for(int i = 0; i < 2; i++)
// for(int j = 0; j < 2; j++) mx[x][i][j] = -INF;
for(int v: g[u]) if(v != p) {
dfs(v, u);
for(int x = 0; x <= lim; x++) {
// ans = max(max(dp[v][x][0][0], dp[v][x][0][1]) + max(mx[lim-x][1][0], mx[lim-x][1][1] + a[v]), ans);
// ans = max(max(mx[lim-x][0][0], mx[lim-x][0][1]) + max(dp[v][x][1][0], dp[v][x][1][1] + a[u]), ans);
// cout << u << ' ' << x << ' ' << v << ' ' << ans << endl;
ll res[2][2] = {
{
max(dp[v][x][0][0], dp[v][x][0][1]),
(x > 0 ? max(dp[v][x-1][0][0], dp[v][x-1][0][1]) + s[u]: -INF) // a[v] - a[v] cancel
},
{
max(dp[v][x][1][0], dp[v][x][1][1] + a[u]),
(x > 0 ? max(dp[v][x-1][1][0], dp[v][x-1][1][1] + a[u]) + s[u] - a[v] : -INF)
}
};
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) {
dp[u][x][i][j] = max(res[i][j], dp[u][x][i][j]);
if(dp[u][x][i][j] < 0) dp[u][x][i][j] = -INF;
// cout << u << ' ' << x << ' ' << i << ' ' << j << ' ' << dp[u][x][i][j] << endl;
}
// mx[x][0][0] = max(dp[u][x][0][0], mx[x][0][0]);
// mx[x][0][1] = max(dp[u][x][0][1] + a[p], mx[x][0][1]);
// mx[x][1][0] = max(dp[u][x][1][0], mx[x][1][0]);
// mx[x][1][1] = max(dp[u][x][1][1] + a[p], mx[x][1][1]);
}
}
}
// dp excludes parent, mx doesn't
int main() {
scanf("%d %d", &n, &lim);
for(int i = 1; i <= n; i++) scanf("%d", a+i);
for(int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
s[u] += a[v];
s[v] += a[u];
}
for(int v = 0; v <= n; v++)
for(int x = 0; x <= lim; x++)
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) dp[v][x][i][j] = -INF;
dfs(1, 0);
ans = 0;
for(int x = 0; x <= lim; x++) for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) ans = max(dp[1][x][i][j], ans);
cout << ans;
}
Compilation message
chase.cpp: In function 'int main()':
chase.cpp:58:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &lim);
^
chase.cpp:59:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; i++) scanf("%d", a+i);
^
chase.cpp:61:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324284 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
324284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324284 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
324284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
333528 KB |
Output is correct |
| 2 |
Correct |
293 ms |
333492 KB |
Output is correct |
| 3 |
Correct |
203 ms |
328000 KB |
Output is correct |
| 4 |
Correct |
109 ms |
327584 KB |
Output is correct |
| 5 |
Correct |
319 ms |
327584 KB |
Output is correct |
| 6 |
Correct |
329 ms |
327584 KB |
Output is correct |
| 7 |
Correct |
316 ms |
327584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324284 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
324284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
