Submission #38151

#	Time	Username	Problem	Language	Result	Execution time	Memory
38151		funcsr	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	206 ms	161564 KiB

skyscraper

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#define rep(i,n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
using namespace std;
#define INF 1145141919
#define MOD 1000000007
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }
inline int mul(int x, int y) { return (1LL*x*y) % MOD; }
int N, L;
int A[100];
int dp[101][1001][101][2][2];

int main() {
  cin >> N >> L;
  if (N == 1) {
    cout << 1 << "\n";
    return 0;
  }
  rep(i, N) cin >> A[i];
  sort(A, A+N);
  dp[0][0][0][0][0] = 1;
  rep(i, N) {
    rep(k, L+1) rep(c, N+1) rep(left, 2) rep(right, 2) {
      if (dp[i][k][c][left][right] == 0) continue;
      int cost = (i>0?(A[i]-A[i-1]):0) * (2*c-left-right);
      if (k+cost > L) continue;
      // o-[]-o
      if (c > 0) {
        add(dp[i+1][k+cost][c-1][left][right], mul(dp[i][k][c][left][right], c-1));
      }
      // o-[]-x or x-[]-o
      if (2*c-left-right > 0) {
        add(dp[i+1][k+cost][c][left][right], mul(dp[i][k][c][left][right], 2*c-left-right));
        if (left  == 0) add(dp[i+1][k+cost][c][1][right], dp[i][k][c][left][right]);
        if (right == 0) add(dp[i+1][k+cost][c][left][1],  dp[i][k][c][left][right]);
      }
      // x-[]-x
      if (c+1 <= N && c+1-left-right > 0) {
        add(dp[i+1][k+cost][c+1][left][right], mul(dp[i][k][c][left][right], c+1-left-right));
        if (left  == 0) add(dp[i+1][k+cost][c+1][1][right], dp[i][k][c][left][right]);
        if (right == 0) add(dp[i+1][k+cost][c+1][left][1],  dp[i][k][c][left][right]);
      }
    }
  }
  int s = 0;
  rep(i, L+1) add(s, dp[N][i][1][1][1]);
  cout << s << "\n";
  return 0;
}

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