結果

問題 No.2982 Logic Battle
ユーザー HIcoder
提出日時 2024-12-22 23:03:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,610 bytes
コンパイル時間 1,488 ms
コンパイル使用メモリ 133,328 KB
最終ジャッジ日時 2025-02-26 16:08:52
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cassert>
#include<random>
#include<set>
#include<map>
#include<cassert>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const ll INF=1LL<<62;
typedef pair<int,ll> P;
typedef pair<int,P> PP; 
const ll MOD=998244353;

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};



int main(){
    int N;
    cin>>N;

    vector<vector<ll>> A(N,vector<ll>(3));
    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++){
            cin>>A[i][j];
        }
    }

    vector<vector<unordered_map<ll,ll>>> dp(N+1,vector<unordered_map<ll,ll>>(3,{{0,0}}));//dp[i][p][x]=i番目のモンスターを倒すとき.直前にp種類目のカードを選んだ
    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++){//j種類目を直前で選んだ
            for(int k=0;k<3;k++){//k種類目を今選ぶ
                if(i>0 && j==k) continue;
                for(auto [attack,score]:dp[i][j]){
                    ll c=max(attack+A[i][k]-1,0LL);
                    ll v=attack+A[i][k];
                    dp[i+1][k][c]=max(dp[i+1][k][c],score+v);
                }

            }
        
        }
    }

    ll ans=0;
    for(int i=0;i<3;i++){//最後に選んだのがi
        for(auto [p,v]:dp[N][i]){
            ans=max(ans,v);
        }
    }
    
    cout<<ans<<endl;
}
0