제출 #164687

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
164687	2019-11-22 15:55:48	ttnhuy313	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	2062 ms	173928 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 105, L = 1005, MOD = 1e9 + 7;
int dp[N][L][2][N][2], a[N], n, maxCost;
void add(int &a, int b) {
  a = (a + b) % MOD;
  return;
}
int calc(int pos, int curCost, int l, int k, int r) {
  int nxtCost = curCost;
  if (pos > 1)
    nxtCost += (l + (k << 1) + r) * (a[pos] - a[pos - 1]);
  if (nxtCost > maxCost) return 0;
  if (pos == n)
    return (k == 0 ? 1 : 0);
  if (~dp[pos][curCost][l][k][r]) return dp[pos][curCost][l][k][r];
  int ret = 0;
  add(ret, calc(pos + 1, nxtCost, 1, k, r));
  add(ret, 1LL * calc(pos + 1, nxtCost, 1, k - 1, r) * k % MOD);
  add(ret, calc(pos + 1, nxtCost, l, k, 1));
  add(ret, 1LL * calc(pos + 1, nxtCost, l, k - 1, 1) * k % MOD);
  add(ret, calc(pos + 1, nxtCost, l, k + 1, r));
  add(ret, 1LL * calc(pos + 1, nxtCost, l, k - 1, r) * k * (k - 1) % MOD);
  add(ret, 1LL * calc(pos + 1, nxtCost, l, k, r) * k * 2 % MOD);
  ret %= MOD;
  return dp[pos][curCost][l][k][r] = ret;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80