Submission #74875740

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define T int t;cin>>t;while(t--)

const int N=2e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;

int n,ans;
int l[25];

void dfs(int u,int p,int c){
    if(u==n){
        ans=max(ans,c);
        return;
    }
    int np1=p+l[u];
    if((p>0)!=(np1>0)){
        dfs(u+1,np1,c+1);
    }else{
        dfs(u+1,np1,c);
    }
    int np2=p-l[u];
    if((p>0)!=(np2>0)){
        dfs(u+1,np2,c+1);
    }else{
        dfs(u+1,np2,c);
    }
}

void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>l[i];
        l[i]*=2;
    }
    ans=0;
    dfs(0,1,0);
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //T
    solve();
    return 0;
}

Submission Info

Judge Result