oj.uz

Submission #239602

# Submission time Handle Problem Language Result Execution time Memory
239602 2020-06-16T15:50:39 Z Nightlight Skyscraper (JOI16_skyscraper) C++14
100 / 100
 230 ms 240248 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int N, L;
int A[105];
int diff[105];
long long memo[101][101][1001][3];

long long dp(int n, int cc, int sum, int k) {
  if(sum > L) return 0;
  if(n > N) return cc == 1 && k == 2;
  if(memo[n][cc][sum][k] != -1) return memo[n][cc][sum][k];
  long long res = 0, nxt = sum + (cc * 2 - k) * diff[n];
  //ga nempel :D
  res += dp(n + 1, cc + 1, nxt, k) * (cc + 1 - k);
  //nempel 1
  if(cc > 0)
   res += dp(n + 1, cc, nxt, k) * (cc * 2 - k);
  //gabung
  if(cc > 1)
    res += dp(n + 1, cc - 1, nxt, k) * (cc - 1);
  
  if(k < 2) {
    //di ujung tapi ga gabung
    res += dp(n + 1, cc + 1, nxt, k + 1) * (2 - k);
    //di ujung nempel
    if(cc > 0)
      res += dp(n + 1, cc, nxt, k + 1) * (2 - k);
  }
  return memo[n][cc][sum][k] = res % MOD;
}

int main() {
  memset(memo, -1, sizeof(memo));
  scanf("%d %d", &N, &L);
  if(N == 1) {
    puts("1");
    return 0;
  }
  for(int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
  }
  sort(A + 1, A + N + 1);
  diff[1] = 0;
  for(int i = 2; i <= N; i++) {
    diff[i] = A[i] - A[i - 1];
  }
  cout << dp(1, 0, 0, 0) << "\n";
  cin >> N;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36: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:42: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 136 ms 240120 KB Output is correct
2 Correct 150 ms 240120 KB Output is correct
3 Correct 135 ms 240120 KB Output is correct
4 Correct 134 ms 240120 KB Output is correct
5 Correct 148 ms 240068 KB Output is correct
6 Correct 135 ms 240120 KB Output is correct
7 Correct 127 ms 240120 KB Output is correct
8 Correct 128 ms 240120 KB Output is correct
9 Correct 135 ms 240120 KB Output is correct
10 Correct 137 ms 240248 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 240120 KB Output is correct
2 Correct 134 ms 240120 KB Output is correct
3 Correct 146 ms 240120 KB Output is correct
4 Correct 148 ms 240076 KB Output is correct
5 Correct 148 ms 240120 KB Output is correct
6 Correct 134 ms 240120 KB Output is correct
7 Correct 128 ms 240120 KB Output is correct
8 Correct 128 ms 240248 KB Output is correct
9 Correct 139 ms 240248 KB Output is correct
10 Correct 137 ms 240248 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 240120 KB Output is correct
2 Correct 150 ms 240120 KB Output is correct
3 Correct 135 ms 240120 KB Output is correct
4 Correct 134 ms 240120 KB Output is correct
5 Correct 148 ms 240068 KB Output is correct
6 Correct 135 ms 240120 KB Output is correct
7 Correct 127 ms 240120 KB Output is correct
8 Correct 128 ms 240120 KB Output is correct
9 Correct 135 ms 240120 KB Output is correct
10 Correct 137 ms 240248 KB Output is correct
11 Correct 131 ms 240120 KB Output is correct
12 Correct 134 ms 240120 KB Output is correct
13 Correct 146 ms 240120 KB Output is correct
14 Correct 148 ms 240076 KB Output is correct
15 Correct 148 ms 240120 KB Output is correct
16 Correct 134 ms 240120 KB Output is correct
17 Correct 128 ms 240120 KB Output is correct
18 Correct 128 ms 240248 KB Output is correct
19 Correct 139 ms 240248 KB Output is correct
20 Correct 137 ms 240248 KB Output is correct
21 Correct 129 ms 240120 KB Output is correct
22 Correct 230 ms 240120 KB Output is correct
23 Correct 201 ms 240164 KB Output is correct
24 Correct 190 ms 240120 KB Output is correct
25 Correct 211 ms 240248 KB Output is correct
26 Correct 174 ms 240120 KB Output is correct
27 Correct 164 ms 240156 KB Output is correct
28 Correct 168 ms 240248 KB Output is correct
29 Correct 201 ms 240120 KB Output is correct
30 Correct 214 ms 240248 KB Output is correct