Submission #19722082


Source Code Expand

Copy
#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

Submission Time
Task B - Three Coins
User TyomaR
Language C++ (GCC 9.2.1)
Score 0
Code Size 2844 Byte
Status RE
Exec Time 121 ms
Memory 11628 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 3
RE × 46
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt RE 121 ms 11292 KB
001.txt RE 116 ms 11280 KB
002.txt RE 116 ms 11320 KB
003.txt RE 120 ms 11404 KB
004.txt RE 121 ms 11408 KB
005.txt RE 117 ms 11356 KB
006.txt RE 119 ms 11408 KB
007.txt RE 117 ms 11292 KB
008.txt RE 118 ms 11356 KB
009.txt RE 118 ms 11304 KB
010.txt RE 116 ms 11408 KB
011.txt RE 118 ms 11304 KB
012.txt RE 117 ms 11404 KB
013.txt RE 116 ms 11408 KB
014.txt RE 120 ms 11352 KB
015.txt RE 116 ms 11404 KB
016.txt RE 116 ms 11324 KB
017.txt RE 117 ms 11356 KB
018.txt RE 115 ms 11296 KB
019.txt RE 116 ms 11404 KB
020.txt RE 117 ms 11324 KB
021.txt RE 116 ms 11296 KB
022.txt RE 119 ms 11332 KB
023.txt RE 117 ms 11312 KB
024.txt RE 116 ms 11292 KB
025.txt RE 117 ms 11408 KB
026.txt RE 114 ms 11408 KB
027.txt RE 117 ms 11348 KB
028.txt RE 117 ms 11328 KB
029.txt RE 115 ms 11340 KB
030.txt RE 116 ms 11332 KB
031.txt RE 117 ms 11236 KB
032.txt RE 116 ms 11348 KB
033.txt RE 119 ms 11276 KB
034.txt RE 115 ms 11296 KB
035.txt RE 116 ms 11400 KB
036.txt RE 116 ms 11316 KB
037.txt RE 117 ms 11336 KB
038.txt RE 115 ms 11292 KB
039.txt RE 115 ms 11352 KB
040.txt RE 117 ms 11292 KB
041.txt RE 116 ms 11408 KB
042.txt RE 116 ms 11356 KB
043.txt RE 116 ms 11352 KB
044.txt RE 118 ms 11296 KB
045.txt RE 116 ms 11304 KB
example0.txt AC 14 ms 11588 KB
example1.txt AC 11 ms 11628 KB
example2.txt AC 6 ms 11576 KB