oj.uz

Submission #132784

# Submission time Handle Problem Language Result Execution time Memory
132784 2019-07-19T14:29:55 Z Just_Solve_The_Problem Skyscraper (JOI16_skyscraper) C++11
20 / 100
 904 ms 97660 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e2 + 7;
const int mod = (int)1e9 + 7;

int add(int a, int b) {
  return (a + b) % mod;
}

int mul(int a, int b) {
  return (a * 1LL * b) % mod;
}

int n, l;
int a[N];
int dp[1 << 14][101][15];

int go(int mask, int lst, int sum) {
  if (mask == 0) return 1;
  int &res = dp[mask][sum][lst];
  if (res != -1) return res;
  res = 0;
  for (int i = 0; i < n; i++) {
    if ((mask >> i) & 1 ^ 1) continue;
    int cost = abs(a[lst] - a[i]);
    if (lst == n) cost = 0;
    if (sum + cost <= l)
      res = add(res, go(mask ^ (1 << i), i, sum + cost));
  }
  return res;
}

main() {
  memset(dp, -1, sizeof dp);
  scanf("%d %d", &n, &l);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  if (n <= 8) {
    sort(a, a + n);
    int ans = 0;
    do {
      int sum = 0;
      for (int i = 1; i < n; i++) {
        sum += abs(a[i] - a[i - 1]);
      }
      ans += (sum <= l);
    } while (next_permutation(a, a + n));
    printf("%d", ans);
    return 0;
  }
  if (n > 14) 
    return 0;
  printf("%d\n", go((1 << n) - 1, n, 0));
}

Compilation message

skyscraper.cpp: In function 'int go(int, int, int)':
skyscraper.cpp:26:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     if ((mask >> i) & 1 ^ 1) continue;
         ~~~~~~~~~~~~^~~
skyscraper.cpp: At global scope:
skyscraper.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &l);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 97528 KB Output is correct
2 Correct 83 ms 97660 KB Output is correct
3 Correct 85 ms 97528 KB Output is correct
4 Correct 83 ms 97528 KB Output is correct
5 Correct 84 ms 97400 KB Output is correct
6 Correct 85 ms 97476 KB Output is correct
7 Correct 84 ms 97400 KB Output is correct
8 Correct 85 ms 97656 KB Output is correct
9 Correct 84 ms 97528 KB Output is correct
10 Correct 84 ms 97420 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 97500 KB Output is correct
2 Correct 140 ms 97596 KB Output is correct
3 Correct 609 ms 97588 KB Output is correct
4 Correct 120 ms 97568 KB Output is correct
5 Correct 100 ms 97400 KB Output is correct
6 Correct 584 ms 97548 KB Output is correct
7 Correct 109 ms 97400 KB Output is correct
8 Correct 596 ms 97528 KB Output is correct
9 Correct 904 ms 97528 KB Output is correct
10 Correct 142 ms 97528 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 97528 KB Output is correct
2 Correct 83 ms 97660 KB Output is correct
3 Correct 85 ms 97528 KB Output is correct
4 Correct 83 ms 97528 KB Output is correct
5 Correct 84 ms 97400 KB Output is correct
6 Correct 85 ms 97476 KB Output is correct
7 Correct 84 ms 97400 KB Output is correct
8 Correct 85 ms 97656 KB Output is correct
9 Correct 84 ms 97528 KB Output is correct
10 Correct 84 ms 97420 KB Output is correct
11 Correct 147 ms 97500 KB Output is correct
12 Correct 140 ms 97596 KB Output is correct
13 Correct 609 ms 97588 KB Output is correct
14 Correct 120 ms 97568 KB Output is correct
15 Correct 100 ms 97400 KB Output is correct
16 Correct 584 ms 97548 KB Output is correct
17 Correct 109 ms 97400 KB Output is correct
18 Correct 596 ms 97528 KB Output is correct
19 Correct 904 ms 97528 KB Output is correct
20 Correct 142 ms 97528 KB Output is correct
21 Incorrect 84 ms 97472 KB Output isn't correct
22 Halted 0 ms 0 KB -