Submission #256610

#	Time	Username	Problem	Language	Result	Execution time	Memory
256610		cjoa	Tents (JOI18_tents)	C++11	100 / 100	295 ms	35936 KiB

tents

//#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

const int MOD = 1e9 + 7;

llong Choose2(int n) {
   return n * 1LL * (n-1) / 2;
}

int memo[3004][3004];
int go(int R, int C) {
   assert(R >= 0 && C >= 0);
// if (R < 0 || C < 0) return 0;
   if (R == 0 || C == 0) return 1;
   int& res = memo[R][C];
   if (res < 0) {
      res = go(R-1, C);  // do not place a tent in last row

      // place single tent in last row and one of the remaining columns (and
      // no other in same column
      llong add = go(R-1, C-1) * 4LL * C;
      res = (res + add) % MOD;

      // place two tents in the last row
      if (C >= 2) {
         add = go(R-1, C-2) * Choose2(C);
         res = (res + add) % MOD;
      }
 
      // place two tents in the same column, one of which is in last row
      if (R >= 2) {
         add = go(R-2, C-1) * 1LL * (R-1) * C;
         res = (res + add) % MOD;
      }
   }
   return res;
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int R, C;
   cin >> R >> C;

   memset(memo, -1, sizeof(memo));
   int res = go(R, C);

   // remove case where no tent was placed
   res = (res + MOD - 1) % MOD;

   cout << res << '\n';

   return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52