oj.uz

Submission #1029892

# Submission time Handle Problem Language Result Execution time Memory
1029892 2024-07-21T13:26:33 Z 0pt1mus23 Džumbus (COCI19_dzumbus) C++14
0 / 110
 28 ms 35364 KB 
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n' 
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 1E3 +100, inf = LLONG_MAX, P = 1453;
// const int L = 30;

int val[sze];
vector<int> graph[sze];
int md =0;
int r =0;
void dfs(int node,int par=-1,int d=0){
    if(d>md){
        md=d;
        r=node;
    }
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node,d+1);
        }
    }
}
vector<int> arr;

void fldfs(int node,int par=-1){
    arr.pb(val[node]);
    for(auto v:graph[node]){
        if(v!=par){
            fldfs(v,node);
        }
    }
}

int dp[sze][sze][2][2];
/*
    dp[i][0][x] = i-ci ni kullanmadan x sumuna gelende max cvb
    dp[i][1][x] = i-ci ni kullaninca x sumuna gelende max cvb
*/
int pref[sze];
int mxp[sze];
void cave(){
    int n,m;
    cin>>n>>m;
    
    arr.pb(0);// 1 indexed

    /*
        20 +30 : Tree , Chain

        N<=100 , O(n^4 ) ? O(n^3 * x ) ? x=1 ?
    */
    for(int i=1;i<=n;i++){
        cin>>val[i];
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dfs(1);
    // cout<<r<<endl;
    fldfs(r);
    // for(auto v:arr){
    //     cout<<v<<" ";
    // }
    // cout<<endl;
    // cout<<endl;

    int lim = 1000; // 20 bal
    
    for(int i=1;i<=n;i++){        
        for(int j=arr[i];j<=6;j++){
            
            /*
                00
                10
            */
            dp[i][j][0][0] =  max({(int)0,dp[i-1][j][0][0],dp[i-1][j][0][1],dp[i-1][j][1][0],dp[i-1][j][1][1]});
            dp[i][j][0][1] = ( dp[i-1][j-arr[i]][0][0] !=0 ? dp[i-1][j-arr[i]][0][0]  : -1 );
            dp[i][j][1][1] = max( ( dp[i-1][j-arr[i]][0][1]!=0 ? max((int)0,dp[i-1][j-arr[i]][0][1]) +2 :0) ,
                                  ( dp[i-1][j-arr[i]][1][1]!=0 ? max((int)0,dp[i-1][j-arr[i]][1][1]) +1 :0)
                                );

            mxp[j]= max({dp[i][j][0][0],dp[i][j][0][1],dp[i][j][1][0],dp[i][j][1][1]});

            // cout<<i<<" "<<j<<" :: \n";
            // cout<<"00 : "<<dp[i][j][0][0]<<endl;
            // cout<<"01 : "<<dp[i][j][0][1]<<endl;
            // cout<<"11 : "<<dp[i][j][1][1]<<endl;
        }
    }
    
    // for(int i=1;i<=10;i++){
    //     cout<<mxp[i]<<" ";
    // }
    // cout<<endl;



    int q;
    cin>>q;
    while(q--){
        int s;
        cin>>s;
        cout<<mxp[s]<<endl;

    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);


    while(tt--){
        cave();
    }

    return 0;
}

Compilation message

dzumbus.cpp: In function 'void cave()':
dzumbus.cpp:81:9: warning: unused variable 'lim' [-Wunused-variable]
   81 |     int lim = 1000; // 20 bal
      |         ^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 35364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 35364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 6096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 35364 KB Output isn't correct
2 Halted 0 ms 0 KB -