| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 169974 |
2019-12-23T13:20:56 Z |
Ruxandra985 |
Chase (CEOI17_chase) |
C++14 |
|
794 ms |
524288 KB |
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> v[DIMN];
int frm;
long long dp[2][DIMN][110] , dp2[2][DIMN][110],part[2][DIMN][110] , part2[2][DIMN][110];
long long val[DIMN] , sol;
void dfs (int nod , int tt){
int i , vecin , j;
long long sum;
sum = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
sum += val[vecin];
}
}
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
dfs (vecin , nod);
//if (nod == 2 && vecin == 6)
// printf ("a");
for ( j = 0 ; j <= frm ; j++){
/// caz 1 : ai venit de jos in nod, te duci in jos spre vecin
sol = max(sol , dp[0][nod][j] + part2[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp[0][nod][j] + part2[1][vecin][frm - j]);
if (j){
sol = max(sol , dp[1][nod][j] + part2[0][vecin][frm - j] + val[tt]);
if (frm - j)
sol = max(sol , dp[1][nod][j] + part2[1][vecin][frm - j] + val[tt]);
}
/// caz 2 : ai venit din jos spre vecin , te duci in nod apoi in jos
sol = max(sol , dp2[0][nod][j] + part[0][vecin][frm - j]);
if (frm - j)
sol = max(sol , dp2[0][nod][j] + part[1][vecin][frm - j] + val[nod]);
if (j){
sol = max(sol , dp2[1][nod][j] + part[0][vecin][frm - j] + val[tt] - val[vecin]);
if (frm - j)
sol = max(sol , dp2[1][nod][j] + part[1][vecin][frm - j] + val[tt] + val[nod] - val[vecin]);
}
//if (nod == 2 && vecin == 6 && sol == 48586232910)
// printf ("%d ",j);
}
//printf ("%d %lld\n",nod,sol);
/// adaugi vecin la setul de vecini cu care ai uni alti vecini
/// (ce coerenta fusei)
/// presupunem ca din vecin vrei sa te duci in nod
dp[1][nod][1] = max ( dp[1][nod][1] , sum );
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp[0][nod][j] = max( dp[0][nod][j] , dp[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp[0][nod][j] = max( dp[0][nod][j] , dp[1][vecin][j] + val[nod]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp[1][nod][j] = max(dp[1][nod][j] , dp[0][vecin][j-1] + sum - val[vecin]);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp[1][nod][j] = max (dp[1][nod][j] , dp[1][vecin][j-1] + sum - val[vecin] + val[nod]);
}
sol = max(sol , dp[0][nod][j]);
if (j)
sol = max(sol , dp[1][nod][j] + val[tt]);
part[1][nod][j] = max(part[1][nod][j-1] , dp[1][nod][j]);
part[0][nod][j] = max(part[0][nod][j-1] , dp[0][nod][j]);
}
/// acum calculez dp2 , incep din i, ma duc in jos , consum j
dp2[1][nod][1] = max(dp2[1][nod][1] , sum);
for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[0][vecin][j]);
/// nu ai aplicat nici in nod nici in vecin , ok
if (j)
dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[1][vecin][j]);
/// daca ai aplicat inainte in vecin, jerry nu mai vede in nod
if (j){ /// aplici in nod
/// daca nu am aplicat in vecin inainte
dp2[1][nod][j] = max(dp2[1][nod][j] , dp2[0][vecin][j-1] + sum);
/// daca am aplicat in vecin inainte
/// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
if (j-1)
dp2[1][nod][j] = max (dp2[1][nod][j] , dp2[1][vecin][j-1] + sum);
}
sol = max(sol , dp2[0][nod][j]);
if (j)
sol = max(sol , dp2[1][nod][j] + val[tt]);
part2[1][nod][j] = max(part2[1][nod][j-1] , dp2[1][nod][j]);
part2[0][nod][j] = max(part2[0][nod][j-1] , dp2[0][nod][j]);
}
//printf ("%d %lld\n",nod,sol);
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , x , y;
fscanf (fin,"%d%d",&n,&frm);
for (i=1;i<=n;i++)
fscanf (fin,"%lld",&val[i]);
for (i=1;i<n;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs (1 , 0);
fprintf (fout,"%lld" , sol);
return 0;
}
Compilation message
chase.cpp: In function 'void dfs(int, int)':
chase.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:128:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&frm);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:130:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld",&val[i]);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:132:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
12 ms |
6392 KB |
Output is correct |
| 8 |
Correct |
10 ms |
6392 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
14 ms |
8444 KB |
Output is correct |
| 11 |
Correct |
13 ms |
8492 KB |
Output is correct |
| 12 |
Correct |
12 ms |
8380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
794 ms |
361992 KB |
Output is correct |
| 2 |
Correct |
785 ms |
361772 KB |
Output is correct |
| 3 |
Correct |
469 ms |
8488 KB |
Output is correct |
| 4 |
Runtime error |
787 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
12 ms |
6392 KB |
Output is correct |
| 8 |
Correct |
10 ms |
6392 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
14 ms |
8444 KB |
Output is correct |
| 11 |
Correct |
13 ms |
8492 KB |
Output is correct |
| 12 |
Correct |
12 ms |
8380 KB |
Output is correct |
| 13 |
Correct |
794 ms |
361992 KB |
Output is correct |
| 14 |
Correct |
785 ms |
361772 KB |
Output is correct |
| 15 |
Correct |
469 ms |
8488 KB |
Output is correct |
| 16 |
Runtime error |
787 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
