oj.uz

Submission #133460

# Submission time Handle Problem Language Result Execution time Memory
133460 2019-07-20T19:14:13 Z win11905 Skyscraper (JOI16_skyscraper) C++11
100 / 100
 318 ms 260708 KB 
#include <bits/stdc++.h>
#define long long long 
using namespace std;

const long M = 1e9+7;

const int N = 105;
const int L = 1005;

int n, m;
int arr[N];
long dp[N][N][L][3];

long mic(int i, int j, int k, int l) {
    if(i != 0 && (j <= 0 || l > 2)) return 0;
    long &z = dp[i][j][k][l];
    if(z != -1) return z;
    if(i == n) return (j == 1 && l == 2);
    int v = (arr[i+1] - arr[i]) * (2*j - l) + k;
    if(v > m) return 0;
    z = (2 * j - l) * mic(i+1, j, v, l) % M;
    z = (z + (j + 1 - l) * mic(i+1, j+1, v, l)) % M;
    z = (z + (2 - l) * mic(i+1, j+1, v, l+1)) % M;
    z = (z + (2 - l) * mic(i+1, j, v, l+1)) % M;
    z = (z + (j - 1) * mic(i+1, j-1, v, l)) % M;
    return z;
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", arr+i);
    sort(arr+1, arr+n+1);
    arr[0] = arr[1];
    printf("%lld\n", n == 1 ? 1 : mic(0, 0, 0, 0));
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:32:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", arr+i);
                                 ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 260708 KB Output is correct
2 Correct 214 ms 260472 KB Output is correct
3 Correct 223 ms 260624 KB Output is correct
4 Correct 214 ms 260472 KB Output is correct
5 Correct 210 ms 260472 KB Output is correct
6 Correct 211 ms 260472 KB Output is correct
7 Correct 214 ms 260496 KB Output is correct
8 Correct 213 ms 260588 KB Output is correct
9 Correct 211 ms 260512 KB Output is correct
10 Correct 220 ms 260436 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 260476 KB Output is correct
2 Correct 214 ms 260600 KB Output is correct
3 Correct 221 ms 260504 KB Output is correct
4 Correct 215 ms 260576 KB Output is correct
5 Correct 212 ms 260516 KB Output is correct
6 Correct 212 ms 260472 KB Output is correct
7 Correct 212 ms 260568 KB Output is correct
8 Correct 239 ms 260572 KB Output is correct
9 Correct 212 ms 260472 KB Output is correct
10 Correct 221 ms 260636 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 260708 KB Output is correct
2 Correct 214 ms 260472 KB Output is correct
3 Correct 223 ms 260624 KB Output is correct
4 Correct 214 ms 260472 KB Output is correct
5 Correct 210 ms 260472 KB Output is correct
6 Correct 211 ms 260472 KB Output is correct
7 Correct 214 ms 260496 KB Output is correct
8 Correct 213 ms 260588 KB Output is correct
9 Correct 211 ms 260512 KB Output is correct
10 Correct 220 ms 260436 KB Output is correct
11 Correct 217 ms 260476 KB Output is correct
12 Correct 214 ms 260600 KB Output is correct
13 Correct 221 ms 260504 KB Output is correct
14 Correct 215 ms 260576 KB Output is correct
15 Correct 212 ms 260516 KB Output is correct
16 Correct 212 ms 260472 KB Output is correct
17 Correct 212 ms 260568 KB Output is correct
18 Correct 239 ms 260572 KB Output is correct
19 Correct 212 ms 260472 KB Output is correct
20 Correct 221 ms 260636 KB Output is correct
21 Correct 227 ms 260548 KB Output is correct
22 Correct 318 ms 260444 KB Output is correct
23 Correct 304 ms 260600 KB Output is correct
24 Correct 279 ms 260472 KB Output is correct
25 Correct 281 ms 260528 KB Output is correct
26 Correct 265 ms 260604 KB Output is correct
27 Correct 237 ms 260472 KB Output is correct
28 Correct 248 ms 260588 KB Output is correct
29 Correct 288 ms 260532 KB Output is correct
30 Correct 280 ms 260472 KB Output is correct