oj.uz

Submission #132781

# Submission time Handle Problem Language Result Execution time Memory
132781 2019-07-19T14:28:25 Z Just_Solve_The_Problem Skyscraper (JOI16_skyscraper) C++11
15 / 100
 825 ms 97628 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 > 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 97528 KB Output is correct
2 Correct 80 ms 97528 KB Output is correct
3 Correct 80 ms 97500 KB Output is correct
4 Correct 80 ms 97528 KB Output is correct
5 Correct 81 ms 97500 KB Output is correct
6 Correct 80 ms 97408 KB Output is correct
7 Correct 81 ms 97500 KB Output is correct
8 Correct 81 ms 97552 KB Output is correct
9 Incorrect 82 ms 97424 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 97400 KB Output is correct
2 Correct 119 ms 97520 KB Output is correct
3 Correct 558 ms 97628 KB Output is correct
4 Correct 115 ms 97528 KB Output is correct
5 Correct 97 ms 97532 KB Output is correct
6 Correct 557 ms 97628 KB Output is correct
7 Correct 104 ms 97532 KB Output is correct
8 Correct 522 ms 97528 KB Output is correct
9 Correct 825 ms 97628 KB Output is correct
10 Correct 124 ms 97400 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 97528 KB Output is correct
2 Correct 80 ms 97528 KB Output is correct
3 Correct 80 ms 97500 KB Output is correct
4 Correct 80 ms 97528 KB Output is correct
5 Correct 81 ms 97500 KB Output is correct
6 Correct 80 ms 97408 KB Output is correct
7 Correct 81 ms 97500 KB Output is correct
8 Correct 81 ms 97552 KB Output is correct
9 Incorrect 82 ms 97424 KB Output isn't correct
10 Halted 0 ms 0 KB -