Submission #2265100
Source Code Expand
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2003,p=1000000007;
int f[2][N],i,j,k,n,m,X,Y,K,an;
bool l;
char c;
inline char getc()
{
#define VV 10000000
static char s[VV],*l=s,*r=s;
if (l==r)
l=s,r=s+fread(s,1,VV,stdin);
return l==r?0:*l++;
}
int read(){ int z=0; do c=getc(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getc(); return z; }
void plus(int &a,int b){ a+=b,a-=a<p?0:p; }
int minus(int a,int b){ a-=b,a+=a<0?p:0; return a; }
int main()
{
n=read(),m=read(),K=read();
if (!n||!m)
{
puts("1");
return 0;
}
--m,--K;
X=(n+m)/K;
f[0][0]=1;
for (i=1;i<=X;++i)
{
l=!l;
Y=min(n,i*K);
for (j=1;j<=Y;++j)
plus(f[!l][j],f[!l][j-1]);
for (j=0;j<=Y;++j)
{
f[l][j]=minus(f[!l][j],j<K+1?0:f[!l][j-K-1]);
if (j&&i*K-j<=m&&j%K==n%K&&(i*K-j)%K==m%K)
plus(an,minus(f[l][j],minus(f[!l][j],f[!l][j-1])));
}
}
printf("%d\n",an);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Eternal Average |
User |
jjb |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
972 Byte |
Status |
AC |
Exec Time |
84 ms |
Memory |
128 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 |
0 ms |
128 KB |
02.txt |
AC |
84 ms |
128 KB |
03.txt |
AC |
0 ms |
128 KB |
04.txt |
AC |
1 ms |
128 KB |
05.txt |
AC |
36 ms |
128 KB |
06.txt |
AC |
0 ms |
128 KB |
07.txt |
AC |
3 ms |
128 KB |
08.txt |
AC |
1 ms |
128 KB |
09.txt |
AC |
2 ms |
128 KB |
10.txt |
AC |
2 ms |
128 KB |
11.txt |
AC |
1 ms |
128 KB |
12.txt |
AC |
1 ms |
128 KB |
13.txt |
AC |
1 ms |
128 KB |
14.txt |
AC |
1 ms |
128 KB |
15.txt |
AC |
1 ms |
128 KB |
16.txt |
AC |
0 ms |
128 KB |
17.txt |
AC |
1 ms |
128 KB |
18.txt |
AC |
1 ms |
128 KB |
19.txt |
AC |
16 ms |
128 KB |
20.txt |
AC |
9 ms |
128 KB |
21.txt |
AC |
0 ms |
128 KB |
22.txt |
AC |
8 ms |
128 KB |
23.txt |
AC |
1 ms |
128 KB |
24.txt |
AC |
1 ms |
128 KB |
s1.txt |
AC |
0 ms |
128 KB |
s2.txt |
AC |
0 ms |
128 KB |
s3.txt |
AC |
1 ms |
128 KB |