oj.uz

Submission #168880

# Submission time Handle Problem Language Result Execution time Memory
168880 2019-12-16T21:21:09 Z triplem5ds Tents (JOI18_tents) C++14
48 / 100
 369 ms 111480 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[305][305][305];
int n, m;
int solve(int col, int emptyRows, int eastRows){
  if(col == m)return 1;
  int &ret = dp[col][emptyRows][eastRows];
  if(~ret)
    return ret;
  ///put nothing
  ret = solve(col+1,emptyRows,eastRows);
  ///put two S and N have to be emptyRows
  if(emptyRows>=2)
    ret = (ret + solve(col+1,emptyRows-2,eastRows) * 1ll * emptyRows * (emptyRows-1)/2) % MOD;
  ///put an S or an N
  if(emptyRows)
    ret = (ret + solve(col+1,emptyRows-1,eastRows) * 3ll * emptyRows)%MOD;
  ///put an E
  if(emptyRows)
    ret = (ret + solve(col+1,emptyRows-1,eastRows+1)*1ll*emptyRows)%MOD;
  ///put a W in an east
  if(eastRows)
    ret = (ret + solve(col+1,emptyRows,eastRows-1)*1ll*eastRows)%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(0,n,0)-1<<'\n';

  return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 111480 KB Output is correct
2 Correct 94 ms 111352 KB Output is correct
3 Correct 94 ms 111352 KB Output is correct
4 Correct 94 ms 111352 KB Output is correct
5 Correct 110 ms 111356 KB Output is correct
6 Correct 103 ms 111476 KB Output is correct
7 Correct 120 ms 111352 KB Output is correct
8 Correct 96 ms 111352 KB Output is correct
9 Correct 94 ms 111352 KB Output is correct
10 Correct 129 ms 111324 KB Output is correct
11 Correct 94 ms 111352 KB Output is correct
12 Correct 369 ms 111324 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 111480 KB Output is correct
2 Correct 94 ms 111352 KB Output is correct
3 Correct 94 ms 111352 KB Output is correct
4 Correct 94 ms 111352 KB Output is correct
5 Correct 110 ms 111356 KB Output is correct
6 Correct 103 ms 111476 KB Output is correct
7 Correct 120 ms 111352 KB Output is correct
8 Correct 96 ms 111352 KB Output is correct
9 Correct 94 ms 111352 KB Output is correct
10 Correct 129 ms 111324 KB Output is correct
11 Correct 94 ms 111352 KB Output is correct
12 Correct 369 ms 111324 KB Output is correct
13 Incorrect 94 ms 111364 KB Output isn't correct
14 Halted 0 ms 0 KB -