提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114795	2023-10-24 08:09:53	Eug1ena	H	cpp	19/19	AC	49

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr lint mod = 1e9 + 7;
#define all(x) begin(x), end(x)
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define rep2(i, l, r) for(int i = int(l); i < int(r); i++)
#define repr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define repr2(i, l, r) for(int i = int(r) - 1; i >= int(l); i--)
#define accumulate you cannot use this word!
constexpr int inf9 = 1e9; constexpr lint inf18 = 1e18;
inline void Yes(bool condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class itr> void array_output(itr start, itr goal){ for(auto i = start; i != goal; i++) cout << (i == start ? "" : " ") << (*i); cout << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(b) return gcd(b, a % b); else return a; }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b < a){ a = b; return 1; } return 0; }
inline int has(lint i, int j){ return (i >> j) & 1; }
int dy[4] = {1, 0, -1, 0}; int dx[4] = {0, 1, 0, -1};
bool is_inside(lint y, lint x, lint H, lint W){ return (0 <= y && y < H && 0 <= x && x < W); }

struct io_init {
    io_init() {
        cin.tie(nullptr); cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }
} io_init;

int n;
string s[20];
int len[20];

int dp[128][1 << 16];

int make_str(char at, int bit_used){
    if(dp[at][bit_used] != -1){
        return dp[at][bit_used];
    }
    
    int ans = 0;
    rep(i, n){
        if(!has(bit_used, i) && s[i][0] == at){
            char to = s[i].back();
            chmax(ans, len[i] + make_str(to, bit_used | (1 << i)));
        }
    }
    
    return dp[at][bit_used] = ans;
}

int main(){
    cin >> n;
    rep(i, n){
        cin >> s[i];
        len[i] = int(s[i].size());
    }
    
    rep(i, 128) rep(j, 1 << 16){
        dp[i][j] = -1;
    }
    
    int ans = 0;
    rep(i, 128){
        chmax(ans, make_str(i, 0));
    }
    cout << ans << endl;
}

sample1.txt AC 32
sample2.txt AC 32
sample3.txt AC 39
case1.txt AC 33
case2.txt AC 33
case3.txt AC 36
case4.txt AC 36
case5.txt AC 35
case6.txt AC 49
case7.txt AC 46
case8.txt AC 32
case9.txt AC 34
case10.txt AC 33
case11.txt AC 34
case12.txt AC 35
case13.txt AC 32
case14.txt AC 37
case15.txt AC 36
case16.txt AC 49
49 AC49 AC