oj.uz

Submission #105254

# Submission time Handle Problem Language Result Execution time Memory
105254 2019-04-11T04:33:46 Z he_____he Tents (JOI18_tents) C++14
48 / 100
 2000 ms 24440 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1000000007;
int n,m;
ll d[3005][3005];

int mod(int x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

int main(){
	n=readint(); m=readint();
	d[m][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=m-j;k++){
				if(j<m&&k) d[j][k]=mod(d[j][k]+d[j+1][k-1]*(j+1)%cys);
				if(k<m-j) d[j][k]=mod(d[j][k]+d[j][k+1]*(k+1)%cys);
				if(j+1<m) d[j][k]=mod(d[j][k]+d[j+2][k]*((j+2)*(j+1)/2)%cys);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) ans=mod(ans+d[i][j]*qpow(4,j)%cys);
	printf("%lld\n",mod(ans+cys-1));
	return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:40:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  printf("%lld\n",mod(ans+cys-1));
                  ~~~~~~~~~~~~~~^

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 26 ms 1664 KB Output is correct
6 Correct 11 ms 640 KB Output is correct
7 Correct 25 ms 1408 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 37 ms 1040 KB Output is correct
11 Correct 11 ms 1912 KB Output is correct
12 Correct 139 ms 1952 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 26 ms 1664 KB Output is correct
6 Correct 11 ms 640 KB Output is correct
7 Correct 25 ms 1408 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 37 ms 1040 KB Output is correct
11 Correct 11 ms 1912 KB Output is correct
12 Correct 139 ms 1952 KB Output is correct
13 Correct 128 ms 20988 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Execution timed out 2032 ms 24440 KB Time limit exceeded
16 Halted 0 ms 0 KB -