oj.uz

Submission #168884

# Submission time Handle Problem Language Result Execution time Memory
168884 2019-12-16T23:48:21 Z triplem5ds Tents (JOI18_tents) C++14
100 / 100
 236 ms 36064 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
//#define endl '\n'

using ll = long long;
using db = long double;
using row = vector<int>;
using ii = pair<int, int>;

const int N = 1e5 + 5, M = 1e6 + 5, A = 6561, LG = 18, MOD = 1e9 + 7;
const int BLOCK = 1900;
const int BLOCKN = N / BLOCK + 1;
const long double EPS = 1e-7;
int dp[3005][3005];
int n, m;
int solve(int col, int emptyRows){
  if(col == 0)return 1;
  int &ret = dp[col][emptyRows];
  if(~ret)
    return ret;
  ///put nothing
  ret = solve(col-1,emptyRows);
  ///put two S and N have to be emptyRows
  if(emptyRows>=2)
    ret = (ret + solve(col-1,emptyRows-2) * 1ll * emptyRows * (emptyRows-1)/2) % MOD;
  if(emptyRows)
    ret = (ret + solve(col-1,emptyRows-1) * 4ll * emptyRows)%MOD;
  ///put a E and W combo
  if(emptyRows&&col>=2)
    ret = (ret + solve(col-2,emptyRows-1)*1ll*emptyRows*(col-1))%MOD;
  return ret;
}
int main(){
  #ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  #endif // ONLINE_JUDGE

  cin>>n>>m;
  memset(dp,-1,sizeof dp);
  cout<<solve(m,n)-1<<'\n';

  return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35704 KB Output is correct
2 Correct 32 ms 35704 KB Output is correct
3 Correct 37 ms 35704 KB Output is correct
4 Correct 37 ms 35704 KB Output is correct
5 Correct 32 ms 35704 KB Output is correct
6 Correct 32 ms 35704 KB Output is correct
7 Correct 32 ms 35704 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 32 ms 35704 KB Output is correct
10 Correct 32 ms 35704 KB Output is correct
11 Correct 32 ms 35704 KB Output is correct
12 Correct 33 ms 35704 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35704 KB Output is correct
2 Correct 32 ms 35704 KB Output is correct
3 Correct 37 ms 35704 KB Output is correct
4 Correct 37 ms 35704 KB Output is correct
5 Correct 32 ms 35704 KB Output is correct
6 Correct 32 ms 35704 KB Output is correct
7 Correct 32 ms 35704 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 32 ms 35704 KB Output is correct
10 Correct 32 ms 35704 KB Output is correct
11 Correct 32 ms 35704 KB Output is correct
12 Correct 33 ms 35704 KB Output is correct
13 Correct 32 ms 35832 KB Output is correct
14 Correct 32 ms 35708 KB Output is correct
15 Correct 141 ms 35804 KB Output is correct
16 Correct 42 ms 35832 KB Output is correct
17 Correct 63 ms 35832 KB Output is correct
18 Correct 66 ms 35852 KB Output is correct
19 Correct 163 ms 35916 KB Output is correct
20 Correct 146 ms 35900 KB Output is correct
21 Correct 110 ms 35960 KB Output is correct
22 Correct 96 ms 35880 KB Output is correct
23 Correct 43 ms 35704 KB Output is correct
24 Correct 236 ms 36064 KB Output is correct
25 Correct 181 ms 35960 KB Output is correct
26 Correct 200 ms 35832 KB Output is correct
27 Correct 229 ms 35972 KB Output is correct