oj.uz

Submission #38127

# Submission time Handle Problem Language Result Execution time Memory
38127 2018-01-02T02:59:12 Z funcsr Skyscraper (JOI16_skyscraper) C++14
5 / 100
 2000 ms 194144 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; }
int N, L;
int A[100];
//#define MAX_L 2800
#define MAX_L 1500
int dp[2][1<<14][MAX_L+1];

int main() {
  cin >> N >> L;
  if (N > 14) abort();
  rep(i, N) cin >> A[i];
  sort(A, A+N, greater<int>());
  int lo = A[N-1], hi = A[0];
  if (hi-lo > L) {
    cout << 0 << "\n";
    return 0;
  }
  rep(i, N) A[i] -= lo;
  dp[0][0][0] = 1;
  rep(i, N) {
    rep(j, 1<<N) rep(k, MAX_L+1) dp[1][j][k] = 0;
    rep(S, 1<<N) {
      rep(pos, N) {
        if ((S>>pos)&1) continue;
        int left = 0, right = 0;
        if (pos > 0) left = ((S>>(pos-1))&1) ? -1 : 1;
        if (pos+1 < N) right = ((S>>(pos+1))&1) ? -1 : 1;
        int e = A[i]*(left+right);
        int nS = S|(1<<pos);
        for (int k=max(-e, 0); k+e<=MAX_L; k++) {
          add(dp[1][nS][k+e], dp[0][S][k]);
        }
      }
    }
    swap(dp[0], dp[1]);
  }
  int s = 0;
  rep(i, L+1) add(s, dp[0][(1<<N)-1][i]);
  cout << s << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 194144 KB Output is correct
2 Correct 86 ms 194144 KB Output is correct
3 Correct 143 ms 194144 KB Output is correct
4 Correct 269 ms 194144 KB Output is correct
5 Correct 369 ms 194144 KB Output is correct
6 Correct 379 ms 194144 KB Output is correct
7 Correct 0 ms 194144 KB Output is correct
8 Correct 386 ms 194144 KB Output is correct
9 Correct 369 ms 194144 KB Output is correct
10 Correct 359 ms 194144 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1423 ms 194144 KB Output is correct
2 Execution timed out 2000 ms 194144 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 194144 KB Output is correct
2 Correct 86 ms 194144 KB Output is correct
3 Correct 143 ms 194144 KB Output is correct
4 Correct 269 ms 194144 KB Output is correct
5 Correct 369 ms 194144 KB Output is correct
6 Correct 379 ms 194144 KB Output is correct
7 Correct 0 ms 194144 KB Output is correct
8 Correct 386 ms 194144 KB Output is correct
9 Correct 369 ms 194144 KB Output is correct
10 Correct 359 ms 194144 KB Output is correct
11 Correct 1423 ms 194144 KB Output is correct
12 Execution timed out 2000 ms 194144 KB Execution timed out
13 Halted 0 ms 0 KB -