oj.uz

답안 #38145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38145 2018-01-02T05:11:05 Z funcsr Skyscraper (JOI16_skyscraper) C++14
20 / 100
 1293 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) {
      if (__builtin_popcount(S) != i) continue;
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 194144 KB Output is correct
2 Correct 96 ms 194144 KB Output is correct
3 Correct 139 ms 194144 KB Output is correct
4 Correct 279 ms 194144 KB Output is correct
5 Correct 363 ms 194144 KB Output is correct
6 Correct 356 ms 194144 KB Output is correct
7 Correct 0 ms 194144 KB Output is correct
8 Correct 349 ms 194144 KB Output is correct
9 Correct 353 ms 194144 KB Output is correct
10 Correct 359 ms 194144 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 659 ms 194144 KB Output is correct
2 Correct 1196 ms 194144 KB Output is correct
3 Correct 1193 ms 194144 KB Output is correct
4 Correct 1239 ms 194144 KB Output is correct
5 Correct 1289 ms 194144 KB Output is correct
6 Correct 1293 ms 194144 KB Output is correct
7 Correct 1223 ms 194144 KB Output is correct
8 Correct 1216 ms 194144 KB Output is correct
9 Correct 1219 ms 194144 KB Output is correct
10 Correct 1159 ms 194144 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 194144 KB Output is correct
2 Correct 96 ms 194144 KB Output is correct
3 Correct 139 ms 194144 KB Output is correct
4 Correct 279 ms 194144 KB Output is correct
5 Correct 363 ms 194144 KB Output is correct
6 Correct 356 ms 194144 KB Output is correct
7 Correct 0 ms 194144 KB Output is correct
8 Correct 349 ms 194144 KB Output is correct
9 Correct 353 ms 194144 KB Output is correct
10 Correct 359 ms 194144 KB Output is correct
11 Correct 659 ms 194144 KB Output is correct
12 Correct 1196 ms 194144 KB Output is correct
13 Correct 1193 ms 194144 KB Output is correct
14 Correct 1239 ms 194144 KB Output is correct
15 Correct 1289 ms 194144 KB Output is correct
16 Correct 1293 ms 194144 KB Output is correct
17 Correct 1223 ms 194144 KB Output is correct
18 Correct 1216 ms 194144 KB Output is correct
19 Correct 1219 ms 194144 KB Output is correct
20 Correct 1159 ms 194144 KB Output is correct
21 Runtime error 0 ms 194144 KB Execution killed because of forbidden syscall gettid (186)
22 Halted 0 ms 0 KB -