結果

問題 No.319 happy b1rthday 2 me
ユーザー yuppe19 😺
提出日時 2016-03-24 19:47:27
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,560 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 53,684 KB
最終ジャッジ日時 2024-11-14 19:36:01
合計ジャッジ時間 1,172 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘i64 f(i64)’:
main.cpp:15:3: error: ‘vector’ was not declared in this scope
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |   ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <algorithm>
  +++ |+#include <vector>
    3 | using namespace std;
main.cpp:15:34: error: expected primary-expression before ‘>>’ token
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |                                  ^~
main.cpp:15:36: error: expected primary-expression before ‘>>’ token
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |                                    ^~
main.cpp:15:71: error: expected primary-expression before ‘>>’ token
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |                                                                       ^~
main.cpp:15:73: error: expected primary-expression before ‘>’ token
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |                                                                         ^
main.cpp:15:95: error: expected primary-expression before ‘>>’ token
   15 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
      |                                                                                               ^~
main.cpp:15:111: error: expec

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;
template<typename T>
class Range{private:struct I{T x;T operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:Range(T n):i({0}),n({n}){}Range(T i,T n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
using range = Range<i64>;
// '12'
i64 f(i64 x) {
string s = to_string(x);
int n = s.size();
vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]
dp[0][0][0][0] = 1;
for(auto&& i : range(n)) {
for(auto&& j : range(2)) {
for(auto&& is1 : range(2)) {
for(auto&& cnt12 : range(n)) {
if(!dp[i][j][is1][cnt12]) { continue; }
for(auto&& d : range(j?10:s[i]-'0'+1)) {
int flag = j || d < s[i] - '0',
nis1 = d==1,
ncnt12 = cnt12 + (is1 && d==2);
dp[i+1][flag][nis1][ncnt12] += dp[i][j][is1][cnt12];
}
}
}
}
}
i64 res = 0;
for(auto&& j : range(2)) {
for(auto&& is1 : range(2)) {
for(auto&& cnt12 : range(n+1)) {
res += dp[n][j][is1][cnt12] * cnt12;
}
}
}
return res;
}
// 22
i64 g(i64 x) {
string s = to_string(x);
int n = s.size();
vector<vector<vector<vector<vector<i64>>>>> dp(n+1, vector<vector<vector<vector<i64>>>>(2, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2,
      vector<i64>(2, 0))))); // dp[n+1][2][2][2][2]
dp[0][0][0][0][0] = 1;
for(auto&& i : range(n)) {
for(auto&& j : range(2)) {
for(auto&& nuke0 : range(2)) {
for(auto&& start2 : range(2)) {
for(auto&& end2 : range(2)) {
if(!dp[i][j][nuke0][start2][end2]) { continue; }
for(auto&& d : range(j?10:s[i]-'0'+1)) {
int flag = j || d < s[i] - '0',
n_nuke0 = nuke0 || d > 0,
nstart2 = start2 || (!nuke0 && d==2),
nend2 = d == 2;
dp[i+1][flag][n_nuke0][nstart2][nend2] += dp[i][j][nuke0][start2][end2];
}
}
}
}
}
}
i64 res = 0;
for(auto&& j : range(2)) {
for(auto&& nuke0 : range(2)) {
res += dp[n][j][nuke0][1][1];
}
}
return res;
}
int main(void) {
i64 a, b; scanf("%lld%lld", &a, &b);
i64 x = f(b) - f(a-1),
y = g(b) - g(a);
i64 res = x + y;
printf("%lld\n", res);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0