結果
問題 | No.295 hel__world |
ユーザー | okaduki |
提出日時 | 2017-12-03 03:59:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 645 ms / 5,000 ms |
コード長 | 2,483 bytes |
コンパイル時間 | 2,481 ms |
コンパイル使用メモリ | 179,112 KB |
実行使用メモリ | 18,396 KB |
最終ジャッジ日時 | 2024-11-28 08:11:46 |
合計ジャッジ時間 | 5,328 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h>using namespace std;using VI = vector<int>;using VVI = vector<VI>;using PII = pair<int, int>;using LL = long long;using VL = vector<LL>;using VVL = vector<VL>;using PLL = pair<LL, LL>;using VS = vector<string>;#define ALL(a) begin((a)),end((a))#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define EB emplace_back#define MP make_pair#define SZ(a) int((a).size())#define SORT(c) sort(ALL((c)))#define RSORT(c) sort(RALL((c)))#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define FF first#define SS secondtemplate<class S, class T>istream& operator>>(istream& is, pair<S,T>& p){return is >> p.FF >> p.SS;}template<class S, class T>ostream& operator<<(ostream& os, const pair<S,T>& p){return os << p.FF << " " << p.SS;}template<class T>void maxi(T& x, T y){if(x < y) x = y;}template<class T>void mini(T& x, T y){if(x > y) x = y;}const double EPS = 1e-10;const double PI = acos(-1.0);const LL MOD = 1e9+7;using LLL = __int128;const LLL MAX = 1ll<<62;LLL solve(LLL rest, LLL sum, VL& vs){if(rest == 0 || vs.empty()) return 1;if(rest > 1e7){if(SZ(vs) > 2) return MAX; // = rest ^ SZ(vs)if(SZ(vs) == 2){if(vs[0] == 1 && vs[1] == 1)return rest / 2 * (rest - rest/2);return MAX;}else{if(vs[0] == 1) return rest;if(vs[0] == 2) return rest * (rest-1) / 2;else return MAX; // = rest^3}}using FRAC = pair<LLL,LLL>; // first / secondauto lt = [](const FRAC& l, const FRAC& r){return l.first * r.second < r.first * l.second;};priority_queue<FRAC,vector<FRAC>,decltype(lt)> pq(lt);for(LL v: vs)pq.push(MP(v+1, 1));rest -= sum;LLL res = 1;while(rest){--rest;auto p = pq.top();pq.pop();res = res * p.first / p.second;if(res >= MAX) break;pq.push(MP(p.first+1, p.second+1));}return res;}int main(){cin.tie(0);ios_base::sync_with_stdio(false);VL S(26);REP(i,26) cin >> S[i];string T;cin >> T;VL sum(26);VVL vs(26);REP(i,SZ(T)){int c = T[i] - 'a';sum[c]++;if(!i || T[i] != T[i-1])vs[c].PB(1);elsevs[c].back()++;}REP(i,26) if(S[i] < sum[i]){cout << 0 << endl;return 0;}LLL ans = 1;REP(c,26){LLL res = solve(S[c], sum[c], vs[c]);if(res >= MAX || (ans *= res) >= MAX){cout << "hel" << endl;return 0;}}cout << (LL)(ans) << endl;return 0;}