結果

問題 No.295 hel__world
ユーザー chocorusk
提出日時 2020-02-23 15:18:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 45 ms / 5,000 ms
コード長 3,272 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 124,576 KB
実行使用メモリ 12,612 KB
最終ジャッジ日時 2024-10-10 02:00:04
合計ジャッジ時間 3,439 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

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;
    sort(v.begin(), v.end());
    if(m==1){
        ll ret=1;
        v[0]=min((ll)v[0], x-v[0]);
        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;
    }else if(m==2 && v[0]==1 && v[1]==2){
        ll l=2, r=x;
        auto calc=[&](ll a){
            lll ret=(lll)(x-a)*a;
            if(ret>=INF) return INF;
            ret*=(a-1); ret/=2;
            if(ret>=INF) return INF;
            else return (ll)ret;
        };
        while(r-l>2){
            ll d=(r-l)/3;
            ll b=calc(l+d);
            if(b>=INF) return INF;
            ll c=calc(r-d);
            if(c>=INF) return INF;
            if(b>=c) r-=d;
            else l+=d;
        }
        ll ret=0;
        for(ll i=l; i<=r; i++){
            ret=max(ret, calc(i));
        }
        return ret;
    }else if(m==3 && v[0]==1 && v[1]==1 && v[2]==1){
        lll a=x/3, b=x/3, c=x/3;
        if(x%3>=1) b++;
        if(x%3==2) c++;
        if(a*b>=INF || a*b*c>=INF) return INF;
        else return a*b*c;
    }
    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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0