제출 #169974

#제출 시각아이디문제언어결과실행 시간메모리
169974Ruxandra985Chase (CEOI17_chase)C++14
40 / 100
794 ms524288 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...