oj.uz

Submission #421582

# Submission time Handle Problem Language Result Execution time Memory
421582 2021-06-09T09:27:06 Z Kerim Tents (JOI18_tents) C++17
48 / 100
 370 ms 221144 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=303;
int dp[N][N][N],c[N];
int mod(ll x){
	return (x%INF);
}
int rec(int row,int s,int empty){
	if(!row)return 1;
	int &ret=dp[row][s][empty];
	if(~ret)return ret;
	ret=rec(row-1,s,empty);
	//N
	if(s)
		ret=mod(ret+rec(row-1,s-1,empty)*1LL*s);
	if(empty){
		//E W N
		ret=mod(ret+rec(row-1,s,empty-1)*3LL*empty);
		//S
		ret=mod(ret+rec(row-1,s+1,empty-1)*1LL*empty);
	}
	//EW
	if(empty>=2)
		ret=mod(ret+rec(row-1,s,empty-2)*1LL*c[empty]);
	return ret;
}
int main(){
    //~ freopen("file.in", "r", stdin);
    memset(dp,-1,sizeof dp);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
		c[i]=(i*(i-1))/2;
	printf("%d\n",mod(rec(n,0,m)-1+INF));
	return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109140 KB Output is correct
2 Correct 54 ms 109172 KB Output is correct
3 Correct 55 ms 109140 KB Output is correct
4 Correct 71 ms 109168 KB Output is correct
5 Correct 54 ms 109124 KB Output is correct
6 Correct 78 ms 109240 KB Output is correct
7 Correct 63 ms 109128 KB Output is correct
8 Correct 65 ms 109072 KB Output is correct
9 Correct 53 ms 109124 KB Output is correct
10 Correct 164 ms 109252 KB Output is correct
11 Correct 64 ms 109124 KB Output is correct
12 Correct 370 ms 109072 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109140 KB Output is correct
2 Correct 54 ms 109172 KB Output is correct
3 Correct 55 ms 109140 KB Output is correct
4 Correct 71 ms 109168 KB Output is correct
5 Correct 54 ms 109124 KB Output is correct
6 Correct 78 ms 109240 KB Output is correct
7 Correct 63 ms 109128 KB Output is correct
8 Correct 65 ms 109072 KB Output is correct
9 Correct 53 ms 109124 KB Output is correct
10 Correct 164 ms 109252 KB Output is correct
11 Correct 64 ms 109124 KB Output is correct
12 Correct 370 ms 109072 KB Output is correct
13 Correct 47 ms 109124 KB Output is correct
14 Runtime error 167 ms 221144 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -