結果
| 問題 | No.295 hel__world |
| ユーザー |
 anta
|
| 提出日時 | 2015-10-23 23:50:08 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 55 ms / 5,000 ms |
| コード長 | 5,923 bytes |
| コンパイル時間 | 1,565 ms |
| コンパイル使用メモリ | 113,160 KB |
| 実行使用メモリ | 49,028 KB |
| 最終ジャッジ日時 | 2024-09-13 04:03:42 |
| 合計ジャッジ時間 | 4,036 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 53 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:163:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
163 | scanf("%lld", &S[i]);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:164:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
164 | scanf("%s", T);
| ~~~~~^~~~~~~~~
ソースコード
#include <string>#include <vector>#include <algorithm>#include <numeric>#include <set>#include <map>#include <queue>#include <iostream>#include <sstream>#include <cstdio>#include <cmath>#include <ctime>#include <cstring>#include <cctype>#include <cassert>#include <limits>#include <functional>#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))#if defined(_MSC_VER) || __cplusplus > 199711L#define aut(r,v) auto r = (v)#else#define aut(r,v) __typeof(v) r = (v)#endif#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)#define all(o) (o).begin(), (o).end()#define pb(x) push_back(x)#define mp(x,y) make_pair((x),(y))#define mset(m,v) memset(m,v,sizeof(m))#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLusing namespace std;typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }struct SaturationInt {typedef unsigned long long T; typedef double Float;static T Max;T x;static inline T sat(T x) { return x > Max ? Max : x; }SaturationInt(): x(0) { }SaturationInt(T x_): x(sat(x_)) { }T get() const { return x; }SaturationInt operator+(const SaturationInt &that) const {return SaturationInt(x + that.x);}SaturationInt operator*(const SaturationInt &that) const {return SaturationInt((Float)x * that.x > Max ? Max : x * that.x);}SaturationInt &operator+=(const SaturationInt &that) { return *this = *this + that; }SaturationInt &operator*=(const SaturationInt &that) { return *this = *this * that; }SaturationInt operator^(long long k) const {T r = 1, a = x;while(k) {if(k & 1) r *= a;if(k >>= 1) {if((Float)a * a * r > Max) return SaturationInt(Max);a *= a;}}return SaturationInt(r);}bool operator<(const SaturationInt &that) const {return x < that.x;}};SaturationInt::T SaturationInt::Max = (1ULL << 63) - 1;typedef SaturationInt sint;const int NCR_TABLE_N = 2000;sint nCrTable[NCR_TABLE_N+1][NCR_TABLE_N+1];sint nCr(long long x, long long y) {if(nCrTable[0][0].x == 0) {for(int i = 0; i <= NCR_TABLE_N; i ++) {nCrTable[i][0] = 1;for(int j = 1; j <= i; j ++)nCrTable[i][j] = nCrTable[i-1][j-1] + nCrTable[i-1][j];}}if(x < y) return sint();if(y > x / 2) y = x - y;if(y == 0) return sint(1);if(y == 1) return sint(x);if(y == 2) {long long a[2] = {x, x - 1};a[x % 2] /= 2;return sint(a[0]) * sint(a[1]);}if(y == 3) {long long a[3] = {x, x - 1, x - 2};a[x % 2] /= 2;a[x % 3] /= 3;return sint(a[0]) * sint(a[1]) * sint(a[2]);}if(y == 4) {long long a[4] = {x, x - 1, x - 2, x - 3};a[(x % 2 == x % 4 ? 2 : 0) + x % 2] /= 2;a[x % 3] /= 3;a[x % 4] /= 4;return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]);}if(y == 5) {long long a[5] = {x, x - 1, x - 2, x - 3, x - 4};a[(x % 2 == x % 4 ? 2 : 0) + x % 2] /= 2;a[x % 3] /= 3;a[x % 4] /= 4;a[x % 5] /= 5;return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]) * sint(a[4]);}if(y == 6) {long long a[6] = {x, x - 1, x - 2, x - 3, x - 4, x - 5};a[x % 5] /= 5;rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; }rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; }rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; }rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; }rep(k, 6) { if(a[k] % 3 == 0) a[k] /= 3; break; }rep(k, 6) { if(a[k] % 3 == 0) a[k] /= 3; break; }return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]) * sint(a[4]) * sint(a[5]);}if(x > NCR_TABLE_N) {return sint(sint::Max);} else {return nCrTable[(int)x][(int)y];}}template<typename T>vector<pair<T,int> > runLength(const T a[], int n) {vector<pair<T,int> > r;if(n <= 0) return r;int cnt = 0;for(int i = 0; i <= n; i ++) {if(i == n || (i != 0 && a[i] != a[i-1])) {r.push_back(make_pair(a[i-1], cnt));cnt = 0;}cnt ++;}return r;}sint solve(long long x, int y, int n) {sint ans = 1;ans *= nCr(y + x / n, y) ^ (n - x % n);ans *= nCr(y + x / n + 1, y) ^ (x % n);return ans;}int main() {const int Alphas = 26;char *T = new char[1000001];vector<long long> S(Alphas);for(int i = 0; i < Alphas; ++ i)scanf("%lld", &S[i]);scanf("%s", T);auto runs = runLength(T, strlen(T));vector<vi> lengths(Alphas);for(auto p : runs) {int a = p.first - 'a';S[a] -= p.second;lengths[a].push_back(p.second);}sint ans = 1;rep(a, Alphas) {long long x = S[a];if(x < 0) {ans *= 0;continue;}vi &v = lengths[a];sort(all(v), greater<int>());if(v.empty())continue;auto w = runLength(&v[0], v.size());if(w.size() == 1) {ans *= solve(x, w[0].first, w[0].second);continue;}vector<int> sum(w.size() + 1, 0);for(int i = (int)w.size() - 1; i >= 0; -- i)sum[i] = sum[i+1] + w[i].first * w[i].second;map<long long, sint> dp, ndp;dp[x] = 1;rep(k, w.size()) {int y = w[k].first, n = w[k].second;double ratio = y * n * 1. / sum[k];ndp.clear();for(auto p : dp) {long long remx = p.first;sint t = p.second;long long a = (long long)(remx * ratio);for(long long b = max(0LL, a - 10); b <= min(remx, a + 10); ++ b) {amax(ndp[remx - b], t * solve(b, y, n));}}sint maxi;dp.clear();for(auto it = ndp.rbegin(); it != ndp.rend(); ++ it) {if(maxi < it->second) {maxi = it->second;dp.insert(*it);}}if(maxi.get() >= 1ULL << 62)break;}sint maxi;for(auto p : dp)amax(maxi, p.second);ans *= maxi;}if(ans.get() >= 1ULL << 62) {puts("hel");} else {cout << ans.get() << endl;}return 0;}