oj.uz

Submission #549521

# Submission time Handle Problem Language Result Execution time Memory
549521 2022-04-16T02:04:55 Z theshadow_04 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 349 ms 524288 KB 
// annotshy

#include <bits/stdc++.h>

#define Task "CF"
#define MOD 1000000007
#define pb push_back

using namespace std;

const int maxn = 200005;

int n, l;
int a[maxn];
long long dp[(1 << 14) + 5][20][105];

void Sub1() {
  vector<int> v;
  for(int i = 1; i <= n; ++i) cin >> a[i], v.pb(i);
  int ans = 0;
  do {
    long long res = 0;
    for(int i = 0; i < (int) v.size() - 1; ++ i) res += abs(a[v[i + 1]] - a[v[i]]);
    if(res <= l) ++ ans;
    if(ans > MOD) ans -= MOD;
  } while(next_permutation(v.begin(), v.end()));
  cout << ans << "\n";
}

void Solve(int Test) {
  cin >> n >> l;
  if(n <= 8) {
    Sub1();
    return;
  }
  for(int i = 0; i < n; ++ i) cin >> a[i];
  memset(dp, 0, sizeof dp);
  for(int i = 0; i < n; ++ i) {
    dp[(1 << i)][i][0] = 1;
  }
  for(int mask = 0; mask < (1 << n); ++ mask) {
    for(int last = 0; last < n; ++ last) {
      for(int s = 0; s <= l; ++ s) {
        if(dp[mask][last][s] == 0 || !(mask >> last & 1)) continue;
        for(int nex = 0; nex < n; ++ nex) {
          if((mask >> nex & 1) || s + abs(a[last] - a[nex]) > l) continue;
          (dp[mask + (1 << nex)][nex][s + abs(a[last] - a[nex])] += dp[mask][last][s]) %= MOD;
        }
      }
    }
  }
  long long ans = 0;
  for(int last = 0; last < n; ++ last) {
    for(int s = 0; s <= l; ++ s) {
      (ans += dp[(1 << n) - 1][last][s]) %= MOD;
    }
  }
  cout << ans << "\n";
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  if(fopen(Task".inp", "r")) {
    freopen(Task".inp", "r", stdin);
    freopen(Task".out", "w", stdout);
  }
  int test = 1;
  // cin >> test;
  for(int i = 1; i <= test; ++ i) {
    Solve(i);
  }
}

/*no pain no gain*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen(Task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen(Task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 269748 KB Output is correct
2 Correct 139 ms 269588 KB Output is correct
3 Correct 237 ms 269624 KB Output is correct
4 Correct 136 ms 269772 KB Output is correct
5 Correct 128 ms 269716 KB Output is correct
6 Correct 253 ms 269720 KB Output is correct
7 Correct 133 ms 269676 KB Output is correct
8 Correct 247 ms 269772 KB Output is correct
9 Correct 289 ms 269596 KB Output is correct
10 Correct 152 ms 269712 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 121 ms 269748 KB Output is correct
12 Correct 139 ms 269588 KB Output is correct
13 Correct 237 ms 269624 KB Output is correct
14 Correct 136 ms 269772 KB Output is correct
15 Correct 128 ms 269716 KB Output is correct
16 Correct 253 ms 269720 KB Output is correct
17 Correct 133 ms 269676 KB Output is correct
18 Correct 247 ms 269772 KB Output is correct
19 Correct 289 ms 269596 KB Output is correct
20 Correct 152 ms 269712 KB Output is correct
21 Runtime error 349 ms 524288 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -