oj.uz

Submission #38150

# Submission time Handle Problem Language Result Execution time Memory
38150 2018-01-02T12:37:45 Z funcsr Skyscraper (JOI16_skyscraper) C++14
15 / 100
 3 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
      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) {
        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
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 Incorrect 3 ms 161564 KB Output isn't correct
6 Halted 0 ms 0 KB -

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
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 Incorrect 3 ms 161564 KB Output isn't correct
6 Halted 0 ms 0 KB -