結果

問題 No.295 hel__world
ユーザー chocoruskchocorusk
提出日時 2020-02-23 14:35:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,373 bytes
コンパイル時間 1,304 ms
コンパイル使用メモリ 120,732 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-10-10 01:58:05
合計ジャッジ時間 8,678 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 3 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 280 ms
5,248 KB
testcase_29 TLE -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef __int128_t lll;
const ll INF=1ll<<62;
struct R{
  ll x, y;
  R(ll x, ll y):x(x), y(y){}
  R(ll x):x(x), y(1ll){}
  bool operator==(const R a) const{
    return x*a.y==y*a.x;
  }
  bool operator<(const R a) const{
    return x*a.y<y*a.x;
  }
};
ll solve(ll x, vector<int> v){
    int m=v.size();
    if(m==0) return 1;
    int sum=0;
    for(auto a:v) sum+=a;
    if(x<sum) return 0;
    else if(x==sum) return 1;
    if(m==1){
        ll ret=1;
        for(int i=0; i<v[0]; i++){
            lll ret1=(lll)ret*(x-i)/(i+1);
            if(ret1>=INF) return INF;
            ret=ret1;
        }
        return ret;
    }else if(m==2 && v[0]==1 && v[1]==1){
        lll ret=(lll)(x/2)*((x+1)/2);
        if(ret>=INF) return INF;
        else return ret;
    }
    ll ret=1;
    using Pr=pair<R, int>;
    vector<int> c(m);
    priority_queue<Pr> que;
    for(int i=0; i<m; i++){
        que.push({R(v[i]+1), i});
    }
    for(ll i=0; i<x-sum; i++){
        auto p=que.top(); que.pop();
        int k=p.second;
        lll ret1=(lll)ret*(v[k]+c[k]+1)/(c[k]+1);
        if(ret1>=INF) return INF;
        ret=ret1; c[k]++;
        que.push({R(v[k]+c[k]+1, c[k]+1), k});
    }
    return ret;
}
int main()
{
    ll x[26];
    for(int i=0; i<26; i++) cin>>x[i];
    string t; cin>>t;
    vector<int> v[26];
    int cnt=1;
    for(int i=1; i<t.size(); i++){
        if(t[i]!=t[i-1]){
            v[t[i-1]-'a'].push_back(cnt);
            cnt=0;
        }
        cnt++;
    }
    v[t.back()-'a'].push_back(cnt);
    ll ans=1;
    for(int i=0; i<26; i++){
        ll a=solve(x[i], v[i]);
        if(a==0){
            cout<<0<<endl;
            return 0;
        }else if(ans>INF/a){
            ans=INF;
        }else{
            ans*=a;
        }
    }
    if(ans>=INF) cout<<"hel"<<endl;
    else cout<<ans<<endl;
    return 0;
}
0