Submission #1078904
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first
#ifdef MYDEBUG
#define DBG(...) {string dst__=#__VA_ARGS__;dreplace(dst__);stringstream dss__; dss__<<dst__; debug(dss__,__VA_ARGS__);}
#else
#define DBG(...)
#endif
void debug(stringstream& ds){cerr<<endl;return;}
template<typename F, typename... R>void debug(stringstream& ds,const F& f, const R&... r){string n; ds>>n; cerr<< n <<'='<<f<<' '; debug(ds,r...);}
void dreplace(string &s){int l=s.length(),n=0;for(int i=0; i<l; ++i){if(s[i]=='(')++n;if(s[i]==')')--n;if(s[i]==','&&!n)s[i]=' ';}}
typedef long long LL; typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
typedef pair<int,int>PI; typedef vector<int> VI;
template<typename T> using V = vector<T>;
constexpr LL LINF=334ll<<53; constexpr int INF=15<<26; constexpr LL MOD=1E9+7;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int n,m,k;
cin >> n >> m >> k;
vector<vector<LL>> a (2002,vector<LL>(2002));
auto dp = [&](int x, int y) -> LL& {return (x<0||y<0)?a[0][0]:a[x+1][y+1];};
dp(0,0)=1;
for(int i=0; i<=m+n; i=i+k-1){
int l=max(0,i-m), h=min(i,m);
for(int j=0; j<k; ++j){
dp(l,h)+=dp(l-k+1+j,h-j);
if(dp(l,h)>MOD)dp(l,h)-=MOD;
}
for(int j=max(0,i-m)+1; j<=min(i,n); ++j){
dp(j,i-j)=dp(j-1,i-j+1)+dp(j,i-j-k+1)-dp(j-k,i-j+1);
if(dp(j,i-j)<0)dp(j,i-j)+=MOD;
else if(dp(j,i-j)>MOD)dp(j,i-j)-=MOD;
}
}
LL ans=0;
for(int i=n; i>0; i-=k-1){
for(int j=m; j>0; j-=k-1){
for(int h=1; h<k; ++h){
ans+=dp(i-h,j-k+h);
if(ans>MOD)ans-=MOD;
}
}
}
cout << ans <<"\n";
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Eternal Average |
User |
Hoi_koro |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
1844 Byte |
Status |
AC |
Exec Time |
112 ms |
Memory |
31616 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
42 ms |
31616 KB |
02.txt |
AC |
112 ms |
31616 KB |
03.txt |
AC |
43 ms |
31616 KB |
04.txt |
AC |
42 ms |
31616 KB |
05.txt |
AC |
78 ms |
31616 KB |
06.txt |
AC |
43 ms |
31616 KB |
07.txt |
AC |
42 ms |
31616 KB |
08.txt |
AC |
43 ms |
31616 KB |
09.txt |
AC |
45 ms |
31616 KB |
10.txt |
AC |
44 ms |
31616 KB |
11.txt |
AC |
43 ms |
31616 KB |
12.txt |
AC |
43 ms |
31616 KB |
13.txt |
AC |
43 ms |
31616 KB |
14.txt |
AC |
43 ms |
31616 KB |
15.txt |
AC |
43 ms |
31616 KB |
16.txt |
AC |
43 ms |
31616 KB |
17.txt |
AC |
43 ms |
31616 KB |
18.txt |
AC |
44 ms |
31616 KB |
19.txt |
AC |
46 ms |
31616 KB |
20.txt |
AC |
54 ms |
31616 KB |
21.txt |
AC |
43 ms |
31616 KB |
22.txt |
AC |
54 ms |
31616 KB |
23.txt |
AC |
45 ms |
31616 KB |
24.txt |
AC |
44 ms |
31616 KB |
s1.txt |
AC |
43 ms |
31616 KB |
s2.txt |
AC |
43 ms |
31616 KB |
s3.txt |
AC |
43 ms |
31616 KB |