oj.uz

Submission #38151

# Submission time Handle Problem Language Result Execution time Memory
38151 2018-01-02T12:40:55 Z funcsr Skyscraper (JOI16_skyscraper) C++14
100 / 100
 206 ms 161564 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 161564 KB Output is correct
2 Correct 0 ms 161564 KB Output is correct
3 Correct 0 ms 161564 KB Output is correct
4 Correct 0 ms 161564 KB Output is correct
5 Correct 0 ms 161564 KB Output is correct
6 Correct 3 ms 161564 KB Output is correct
7 Correct 0 ms 161564 KB Output is correct
8 Correct 0 ms 161564 KB Output is correct
9 Correct 0 ms 161564 KB Output is correct
10 Correct 0 ms 161564 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 161564 KB Output is correct
2 Correct 0 ms 161564 KB Output is correct
3 Correct 0 ms 161564 KB Output is correct
4 Correct 0 ms 161564 KB Output is correct
5 Correct 0 ms 161564 KB Output is correct
6 Correct 0 ms 161564 KB Output is correct
7 Correct 0 ms 161564 KB Output is correct
8 Correct 0 ms 161564 KB Output is correct
9 Correct 0 ms 161564 KB Output is correct
10 Correct 0 ms 161564 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 161564 KB Output is correct
2 Correct 0 ms 161564 KB Output is correct
3 Correct 0 ms 161564 KB Output is correct
4 Correct 0 ms 161564 KB Output is correct
5 Correct 0 ms 161564 KB Output is correct
6 Correct 3 ms 161564 KB Output is correct
7 Correct 0 ms 161564 KB Output is correct
8 Correct 0 ms 161564 KB Output is correct
9 Correct 0 ms 161564 KB Output is correct
10 Correct 0 ms 161564 KB Output is correct
11 Correct 0 ms 161564 KB Output is correct
12 Correct 0 ms 161564 KB Output is correct
13 Correct 0 ms 161564 KB Output is correct
14 Correct 0 ms 161564 KB Output is correct
15 Correct 0 ms 161564 KB Output is correct
16 Correct 0 ms 161564 KB Output is correct
17 Correct 0 ms 161564 KB Output is correct
18 Correct 0 ms 161564 KB Output is correct
19 Correct 0 ms 161564 KB Output is correct
20 Correct 0 ms 161564 KB Output is correct
21 Correct 3 ms 161564 KB Output is correct
22 Correct 206 ms 161564 KB Output is correct
23 Correct 166 ms 161564 KB Output is correct
24 Correct 143 ms 161564 KB Output is correct
25 Correct 166 ms 161564 KB Output is correct
26 Correct 143 ms 161564 KB Output is correct
27 Correct 59 ms 161564 KB Output is correct
28 Correct 83 ms 161564 KB Output is correct
29 Correct 136 ms 161564 KB Output is correct
30 Correct 169 ms 161564 KB Output is correct