Submission #19722082

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};

const int N=101,OO=1e18;
int a[N];
vector<int> v[3];
int dp[N][N][N];
int32_t main(){
    int n;
    cin>>n;
    forn(i,n){
        cin>>a[i];
        v[i%3].pb(a[i]);
    }
    forn(i,3)sort(v[i].begin(), v[i].end(),greater<int>());
    forn(i,N)forn(j,N)forn(k,N)dp[i][j][k]=-OO;
    dp[0][0][0]=0;
    int ans=0;
    for(int sum=0;sum<=n;++sum){
        for(int i=0;i<=sum;++i){
            for(int j=0;i+j<=sum;++j){
                int k=sum-i-j;
                if(i>sz(v[0])||j>sz(v[1])||k>sz(v[2]))continue;
                upx(ans,dp[i][j][k]);
                dbg(i,j,k);
                if(i<sz(v[0])&&j<sz(v[1])&&k<sz(v[2])){
                    upx(dp[i+1][j+1][k+1],dp[i][j][k]+v[0][i]+v[1][j]+v[2][k]);
                }
                if(i<sz(v[0])&&j<sz(v[1])&&k){
                    upx(dp[i+1][j+1][k-1],dp[i][j][k]+v[0][i]+v[1][j]-v[2][k-1]);
                }
                if(i<sz(v[0])&&j&&k<sz(v[2])){
                    upx(dp[i+1][j-1][k+1],dp[i][j][k]+v[0][i]-v[1][j-1]+v[2][k]);
                }
                if(i&&j<sz(v[1])&&k<sz(v[2])){
                    upx(dp[i-1][j+1][k+1],dp[i][j][k]-v[0][i-1]+v[1][j]+v[2][k]);
                }
                if(i+1<sz(v[0])){
                    upx(dp[i+2][j][k],dp[i][j][k]+v[0][i]+v[0][i+1]);
                }
                if(j+1<sz(v[1])){
                    upx(dp[i][j+2][k],dp[i][j][k]+v[1][j]+v[1][j+1]);
                }
                if(k+1<sz(v[2])){
                    upx(dp[i][j][k+2],dp[i][j][k]+v[2][k]+v[2][k+1]);
                }
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Submission Info

Judge Result