Submission #5630964
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef vector<pll> vpll;
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
inline void IN(void){
return;
}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
cin >> first;
IN(rest...);
return;
}
inline void OUT(void){
cout << "\n";
return;
}
template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
cout << first << " ";
OUT(rest...);
return;
}
template <typename T>
void vec_print(vector<T> VEC){
REP(i, VEC.size()){
cout << VEC[i] << " ";
}
cout << "\n";
};
template <typename T>
void mat_print(vector<vector<T> > MAT){
REP(i, MAT.size()){
REP(j, MAT[i].size()){
cout << MAT[i][j] << " ";
}
cout << "\n";
}
};
template <typename CLASS1, typename CLASS2>
class HOGE{
public:
CLASS1 key;
CLASS2 value;
HOGE(void){
return;
};
HOGE(CLASS1 key, CLASS2 value){
this->key = key;
this->value = value;
};
~HOGE(void){
return;
};
void print(void){
cout << "key : " << key << ", value : " << value << "\n";
return;
};
bool operator==(const HOGE &obj){
return (this->value == obj.value);
};
bool operator<(const HOGE &obj){
return (this->value < obj.value);
};
bool operator>(const HOGE &obj){
return (this->value > obj.value);
};
};
template <typename CLASS1, typename CLASS2>
bool operator==(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value == hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator<(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value < hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator>(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value > hoge2.value;
};
constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);
int main(){
cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)
ll K,N;
IN(N,K);
vvll dp(N, vll(K, 0)); // i駅まで, 最後の長さがj
dp[0][1] = 1;
deque<ll> que;
que.pb(0);
que.pb(1);
REP(i,K-2) que.pb(0);
ll que_sum = 1;
FOR(i,1,N-1){
que.push_front(que_sum);
ll tmp = que.back(); que.pop_back();
que_sum *= 2;
que_sum -= tmp;
}
ll ans = que_sum - que.back();
/*
FOR(i,1,N-1){
vvll dp_copy = dp;
dp.assign(N, vll(K, 0));
REP(j,K-1){
dp[i][0] += dp_copy[i-1][j]; // not stop at i
dp[i][j+1] += dp_copy[i-1][j]; // stop at i
}
dp[i][0] += dp_copy[i-1][K-1]; // don't stop at i
}
ll ans = 0;
REP(i,K-1){
ans += dp[N-2][i];
}
*/
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - 準急 |
User |
fockl |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3748 Byte |
Status |
RE |
Exec Time |
1651 ms |
Memory |
182260 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
WA |
64 ms |
54912 KB |
01 |
RE |
1328 ms |
-777252 KB |
02 |
RE |
1644 ms |
-778196 KB |
03 |
RE |
1651 ms |
-776784 KB |
04 |
WA |
153 ms |
182260 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |