제출 #44672

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
44672	2018-04-04 17:48:02	IvanC	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	401 ms	321228 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;
typedef long long ll;
const int MAXL = 1002;
const int MAXN = 101;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXN][2][2][MAXL],N,L,V[MAXN];
ll solve(ll pos,ll cmp,ll lcmp,ll rcmp,ll penalty){
  if(cmp < 0) return 0;
  if(dp[pos][cmp][lcmp][rcmp][penalty] != -1) return dp[pos][cmp][lcmp][rcmp][penalty]; 
  ll penalty_now = penalty;
  if(pos > 1) penalty_now += (2*cmp + lcmp + rcmp)*abs(V[pos] - V[pos-1]);
  if(penalty_now > L) return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
  if(pos == N){
    if(cmp == 0) return dp[pos][cmp][lcmp][rcmp][penalty] = 1;
    else return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
  }
  ll tot = 0;
  tot += solve(pos+1,cmp,1,rcmp,penalty_now);
  tot += solve(pos+1,cmp-1,1,rcmp,penalty_now)*cmp;
  tot += solve(pos+1,cmp,lcmp,1,penalty_now);
  tot += solve(pos+1,cmp-1,lcmp,1,penalty_now)*cmp;
  tot += solve(pos+1,cmp,lcmp,rcmp,penalty_now)*(2*cmp);
  tot += solve(pos+1,cmp+1,lcmp,rcmp,penalty_now);
  tot += solve(pos+1,cmp-1,lcmp,rcmp,penalty_now)*cmp*(cmp-1);
  return dp[pos][cmp][lcmp][rcmp][penalty] = (tot % MOD);
}
int main(){
  memset(dp,-1,sizeof(dp));
  cin >> N >> L;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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