Submission #132780

#	Time	Username	Problem	Language	Result	Execution time	Memory
132780		Just_Solve_The_Problem	Skyscraper (JOI16_skyscraper)	C++11	5 / 100	2062 ms	97532 KiB

skyscraper

#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 += 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]);
  }
  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);
}

Compilation message (stderr)

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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80