Submission #1077302
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll mod = 1e9+7;
ll dp[2001][2001];
void add(ll &x,ll y){
x+=y;
x%=mod;
}
int N,M,K;
int main(){
cin>>N>>M>>K;
int D=(N+M-1)/(K-1);
dp[0][0]=1;
ll ans=0;
rep(d,D){
rep(a,N+1){
int b=(K-1)*d-a;
if(!(0<=b&&b<=M)) continue;
rep(k,K){ //K-1 (continue)
int na=a+k,nb=b+(K-1-k);
if(na>N||nb>M) continue;
add(dp[na][nb],dp[a][b]);
}
rep1(k,K-1){ //K (end)
int na=a+k,nb=b+(K-k);
if(na<=N&&nb<=M&&(N-na)%(K-1)==0&&(M-nb)%(K-1)==0) add(ans,dp[a][b]);
}
}
}
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
E - Eternal Average |
User |
sigma425 |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
1187 Byte |
Status |
AC |
Exec Time |
266 ms |
Memory |
31488 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 |
3 ms |
256 KB |
02.txt |
AC |
266 ms |
31488 KB |
03.txt |
AC |
3 ms |
256 KB |
04.txt |
AC |
3 ms |
256 KB |
05.txt |
AC |
190 ms |
31488 KB |
06.txt |
AC |
3 ms |
256 KB |
07.txt |
AC |
12 ms |
4224 KB |
08.txt |
AC |
5 ms |
1024 KB |
09.txt |
AC |
128 ms |
31488 KB |
10.txt |
AC |
125 ms |
31488 KB |
11.txt |
AC |
55 ms |
10880 KB |
12.txt |
AC |
25 ms |
8192 KB |
13.txt |
AC |
108 ms |
27904 KB |
14.txt |
AC |
66 ms |
18816 KB |
15.txt |
AC |
100 ms |
25728 KB |
16.txt |
AC |
3 ms |
256 KB |
17.txt |
AC |
77 ms |
20352 KB |
18.txt |
AC |
30 ms |
7296 KB |
19.txt |
AC |
34 ms |
9856 KB |
20.txt |
AC |
124 ms |
29824 KB |
21.txt |
AC |
3 ms |
256 KB |
22.txt |
AC |
140 ms |
31488 KB |
23.txt |
AC |
104 ms |
28032 KB |
24.txt |
AC |
98 ms |
26368 KB |
s1.txt |
AC |
3 ms |
256 KB |
s2.txt |
AC |
3 ms |
256 KB |
s3.txt |
AC |
4 ms |
1024 KB |