Submission #218707

#	Time	Username	Problem	Language	Result	Execution time	Memory
218707		eriksuenderhauf	Ruins 3 (JOI20_ruins3)	C++11	100 / 100	325 ms	17272 KiB

ruins3

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define trav(x,a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int _i = 1; _i <= (n); _i++) ni(a[_i])
#define nal(a, n) for (int _i = 1; _i <= (n); _i++) nl(a[_i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int N = 2e3 + 5;
const double eps = 1e-9;
int a[N], C[N][N], fac[N], dp[N][N];

int add(int x, int y) { return x+y < mod ? x+y : x+y-mod; }
int mul(int x, int y) { return x*1ll*y % mod; }

int main() {
  fac[0] = C[0][0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = mul(fac[i-1], i);
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = add(C[i-1][j], C[i-1][j-1]);
  }
  int n; ni(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a+i);
  }
  dp[1][1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n+1; j++) {
      if (dp[i][j] == 0)
        continue;
      for (int k = 0; k <= min(n, a[i] - i) - j + 1; k++) {
        int val = mul(mul(dp[i][j], C[2*k][k]), mul(C[a[i]-i-j+1][k], fac[k]));
        dp[i+1][j+k] = add(dp[i+1][j+k], mul(val, k > 0 ? 1 : j - i));
      }
    }
  }
  int ans = dp[n+1][n+1];
  for (int i = 1; i <= n; i++)
    ans = mul(ans, 500000004);
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
ruins3.cpp:49:10: note: in expansion of macro 'ni'
   int n; ni(n);
          ^~
ruins3.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", a+i);
     ~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42