Submission #19722088


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=505,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 WA
Exec Time 703 ms
Memory 1009832 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 5
WA × 44
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 WA 703 ms 1009696 KB
001.txt WA 698 ms 1009720 KB
002.txt WA 695 ms 1009712 KB
003.txt WA 698 ms 1009768 KB
004.txt WA 695 ms 1009704 KB
005.txt WA 699 ms 1009704 KB
006.txt WA 697 ms 1009792 KB
007.txt WA 693 ms 1009716 KB
008.txt WA 699 ms 1009764 KB
009.txt WA 699 ms 1009820 KB
010.txt WA 699 ms 1009752 KB
011.txt WA 700 ms 1009724 KB
012.txt WA 693 ms 1009652 KB
013.txt WA 695 ms 1009788 KB
014.txt WA 698 ms 1009784 KB
015.txt WA 697 ms 1009668 KB
016.txt WA 698 ms 1009696 KB
017.txt WA 696 ms 1009764 KB
018.txt WA 697 ms 1009792 KB
019.txt WA 697 ms 1009832 KB
020.txt WA 694 ms 1009788 KB
021.txt WA 698 ms 1009748 KB
022.txt WA 696 ms 1009712 KB
023.txt WA 696 ms 1009768 KB
024.txt WA 697 ms 1009748 KB
025.txt WA 699 ms 1009748 KB
026.txt WA 696 ms 1009700 KB
027.txt WA 700 ms 1009720 KB
028.txt WA 697 ms 1009700 KB
029.txt WA 694 ms 1009764 KB
030.txt WA 696 ms 1009696 KB
031.txt WA 695 ms 1009788 KB
032.txt WA 698 ms 1009720 KB
033.txt WA 698 ms 1009792 KB
034.txt WA 699 ms 1009768 KB
035.txt AC 703 ms 1009784 KB
036.txt WA 700 ms 1009700 KB
037.txt WA 700 ms 1009700 KB
038.txt WA 703 ms 1009764 KB
039.txt WA 696 ms 1009724 KB
040.txt WA 697 ms 1009656 KB
041.txt WA 697 ms 1009720 KB
042.txt WA 697 ms 1009792 KB
043.txt WA 699 ms 1009752 KB
044.txt WA 695 ms 1009672 KB
045.txt AC 699 ms 1009720 KB
example0.txt AC 542 ms 1009748 KB
example1.txt AC 536 ms 1009744 KB
example2.txt AC 540 ms 1009700 KB