結果

問題 No.1106 🦉 何事もバランスが大事
コンテスト
ユーザー FF256grhy
提出日時 2020-07-04 01:44:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,537 bytes
コンパイル時間 4,235 ms
コンパイル使用メモリ 202,708 KB
最終ジャッジ日時 2025-01-11 15:19:12
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T &  a, U &  ... b) { cin >> a; IN_(b ...); };
template<typename T                > void OUT(T && a            ) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T> T MV(T v) { return v; }
template<typename T, typename ... U> auto MV(T v, int a, U ... b) { return vector<decltype(MV(v, b ...))>(a, MV(v, b ...)); }

int main() {
	const int N = 27;
	
	auto f = [](LL x) -> vector<int> {
		vector<int> v(N);
		inc(i, N) { v[i] = x % 5; x /= 5; }
		inc(i, N - 1) { if(v[i] > 2) { v[i] -= 5; v[i + 1]++; } }
		reverse(ALL(v));
		return v;
	};
	
	auto g = [&](LL x) -> LL {
		x++;
		auto v = f(x);
		auto dp_ = MV<LL>(0, N + 1, 2 * (N + 2) + 1, 2);
		auto dp = [&](int i, int j, int k) -> auto & { return dp_[i][j + N + 2][k]; };
		dp(0, 0, 0) = 1;
		inc(i, N) {
		incII(j, -N, +N) {
		incII(w, -2, +2) {
			if(w == v[i]) { dp(i + 1, j + w, 0) += dp(i, j, 0); }
			if(w <  v[i]) { dp(i + 1, j + w, 1) += dp(i, j, 0); }
			                dp(i + 1, j + w, 1) += dp(i, j, 1);
		}
		}
		}
		return dp(N, 0, 1);
	};
	
	IN(LL, x);
	OUT(g(x) - g(0));
}
0