結果
問題 | No.473 和と積の和 |
ユーザー | しらっ亭 |
提出日時 | 2016-12-23 01:44:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
MLE
(最初)
|
実行時間 | - |
コード長 | 2,602 bytes |
コンパイル時間 | 2,368 ms |
コンパイル使用メモリ | 187,124 KB |
実行使用メモリ | 817,920 KB |
最終ジャッジ日時 | 2024-12-16 02:57:15 |
合計ジャッジ時間 | 19,272 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 1,077 ms
246,144 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 | 3 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 | 2 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 | 8 ms
5,248 KB |
testcase_24 | AC | 14 ms
6,656 KB |
testcase_25 | TLE | - |
testcase_26 | AC | 948 ms
203,264 KB |
testcase_27 | AC | 1,469 ms
327,296 KB |
testcase_28 | AC | 5 ms
5,120 KB |
testcase_29 | AC | 3 ms
5,120 KB |
testcase_30 | AC | 3 ms
5,120 KB |
testcase_31 | AC | 3 ms
5,120 KB |
testcase_32 | AC | 3 ms
5,120 KB |
testcase_33 | AC | 3 ms
5,120 KB |
testcase_34 | AC | 1,579 ms
361,728 KB |
testcase_35 | AC | 1,433 ms
326,912 KB |
testcase_36 | AC | 4 ms
5,120 KB |
testcase_37 | AC | 3 ms
5,120 KB |
testcase_38 | AC | 1,297 ms
300,800 KB |
testcase_39 | AC | 472 ms
112,512 KB |
testcase_40 | AC | 514 ms
122,624 KB |
testcase_41 | AC | 659 ms
152,960 KB |
testcase_42 | AC | 72 ms
24,448 KB |
testcase_43 | AC | 530 ms
129,024 KB |
testcase_44 | AC | 1,251 ms
297,472 KB |
testcase_45 | AC | 4 ms
5,120 KB |
testcase_46 | AC | 15 ms
5,120 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i<int(b);++i) #define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__) #define _rrep2(i,n) _rrep3(i,0,n) #define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define bit(n) (1LL<<(n)) #define sz(x) ((int)(x).size()) #define fst first #define snd second using ll=long long;using pii=pair<int,int>; using vb=vector<bool>;using vs=vector<string>; using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>; using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>; using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>; using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>; template<typename T>T read(){T t;cin>>t;return t;} template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){o<<'('<<p.fst<<", "<<p.snd<<')';return o;} vi E; void calc(int x) { for (int a = 1; ; a++) { ll b = (x - a) / (a + 1); if (b < a) break; if (a * b + a + b == x) { E.emplace_back(a); E.emplace_back(b); } } sort(all(E)); E.erase(unique(E.begin(), E.end()), E.end()); } int f(int x, int a) { int b = (x - a) / (a + 1); if (a + b + a * b == x) return b; return -1; } map<int, int> dp[101]; void Main() { int n = read<int>(); int x = read<int>(); calc(x); int m = sz(E); //cout << "n: "<<n << endl; //cout << "x: "<<x << endl; //cout << "E:"; rep(ii,sz(E)) cout << ' ' << E[ii]; cout << endl; //cout << "m: "<<m << endl; using mii=map<int, int>; vector<vector<mii>> dp(n + 1, vector<mii>(m + 1)); dp[0][0][0] = 1; rep(i, n) rep(j, m) { int e = E[j]; forr(pc, dp[i][j]) { ll p = pc.fst; int c = pc.snd; { ll q = p + e + p * e; if (q <= x) { if (i+1==n && q == x) dp[i+1][j][q] += c; else { if (q + e + q * e <= x) dp[i+1][j][q] += c; } } } { if (j+1<=m) { if (p == x) dp[i][j+1][p] += c; else if (j+1<m) { int f = E[j+1]; if (f * p + f + p <= x) dp[i][j+1][p] += c; } } } } } int ans = 0; rep(i, m+1) { ans += dp[n][i][x]; } cout << ans << endl; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }