Submission #169979

#	Time	Username	Problem	Language	Result	Execution time	Memory
169979		Ruxandra985	Chase (CEOI17_chase)	C++14	100 / 100	679 ms	281060 KiB

chase

#include <bits/stdc++.h>
#define DIMN 100001
#define DIMF 101
using namespace std;
vector <int> v[DIMN];
int frm;
long long dp[2][DIMN][DIMF] , dp2[2][DIMN][DIMF];
//long long dp[2][DIMN][DIMF] , dp2[2][DIMN][DIMF];
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] + dp2[0][vecin][frm - j]);
                if (frm - j)
                    sol = max(sol , dp[0][nod][j] + dp2[1][vecin][frm - j]);

                if (j){
                    sol = max(sol , dp[1][nod][j] + dp2[0][vecin][frm - j] + val[tt]);
                    if (frm - j)
                        sol = max(sol , dp[1][nod][j] + dp2[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] + dp[0][vecin][frm - j]);
                if (frm - j)
                    sol = max(sol , dp2[0][nod][j] + dp[1][vecin][frm - j] + val[nod]);

                if (j){
                    sol = max(sol , dp2[1][nod][j] + dp[0][vecin][frm - j] + val[tt] - val[vecin]);
                    if (frm - j)
                        sol = max(sol , dp2[1][nod][j] + dp[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]);
                if (j >= 2){
                    dp[1][nod][j] = max(dp[1][nod][j-1] , dp[1][nod][j]);
                    dp[0][nod][j] = max(dp[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]);
                if (j >= 2){
                    dp2[1][nod][j] = max(dp2[1][nod][j-1] , dp2[1][nod][j]);
                    dp2[0][nod][j] = max(dp2[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 (stderr)

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
chase.cpp:20: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:134: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:136: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:138: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);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30