oj.uz

Submission #44599

# Submission time Handle Problem Language Result Execution time Memory
44599 2018-04-03T17:42:24 Z choikiwon Skyscraper (JOI16_skyscraper) C++17
20 / 100
 2000 ms 491404 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int offset = 1000;

int N, L;
int A[102];

int cc[102][102][3010][2][2];
int dp(int n, int d, int sum, int s, int e) {
    if(sum >= 3010) return 0;
    if(n == N) return !d && sum <= L + offset && s && e;
    int &ret = cc[n][d][sum][s][e];
    if(ret != -1) return ret;

    int l = d;
    int r = d + e - s;

    if(n && l <= 0 && r <= 0) return ret = 0;

    ret = 0;
    if(!s) {
        ret += dp(n + 1, d + 1, A[n] + sum + 2 * (A[n + 1] - A[n]) * (d + 1), 1, e);
        ret %= mod;
        if(r) {
            ret += 1LL * (n == N - 1? r : r - e) * dp(n + 1, d, A[n] + sum + 2 * (A[n + 1] - A[n]) * d, 1, e) % mod;
            ret %= mod;
        }
    }
    if(!e) {
        ret += dp(n + 1, d, -A[n] + sum + 2 * (A[n + 1] - A[n]) * d, s, 1);
        ret %= mod;
        if(l) {
            ret += 1LL * (n == N - 1? l : l - s) * dp(n + 1, d - 1, -A[n] + sum + 2 * (A[n + 1] - A[n]) * (d - 1), s, 1) % mod;
            ret %= mod;
        }
    }
    if(l) {
        ret += 1LL * l * dp(n + 1, d, sum + 2 * (A[n + 1] - A[n]) * d, s, e) % mod;
        ret %= mod;
        if(s && !e) {
            ret += 1LL * r * dp(n + 1, d - 1, sum + 2 * (A[n + 1] - A[n]) * (d - 1), s, e) % mod;
            ret %= mod;
        }
        if(r) {
            ret += 1LL * min(l, r) * (n == N - 1? r : r - 1) % mod * dp(n + 1, d - 1, sum + 2 * (A[n + 1] - A[n]) * (d - 1), s, e) % mod;
            ret %= mod;
        }
    }
    if(r) {
        ret += 1LL * r * dp(n + 1, d, sum + 2 * (A[n + 1] - A[n]) * d, s, e) % mod;
        ret %= mod;
    }
    ret += dp(n + 1, d + 1, sum + 2 * (A[n + 1] - A[n]) * (d + 1), s, e);
    ret %= mod;

    return ret;
}

int main() {
    scanf("%d %d", &N, &L);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    if(N == 1) {
        printf("1");
        return 0;
    }

    sort(A, A + N);

    memset(cc, -1, sizeof(cc));
    printf("%d", dp(0, 0, offset, 0, 0));
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &L);
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:65:14: 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 2 ms 376 KB Output is correct
2 Correct 349 ms 490600 KB Output is correct
3 Correct 343 ms 490656 KB Output is correct
4 Correct 363 ms 490676 KB Output is correct
5 Correct 351 ms 490936 KB Output is correct
6 Correct 340 ms 490968 KB Output is correct
7 Correct 349 ms 490988 KB Output is correct
8 Correct 334 ms 490988 KB Output is correct
9 Correct 340 ms 491068 KB Output is correct
10 Correct 381 ms 491100 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 491100 KB Output is correct
2 Correct 346 ms 491128 KB Output is correct
3 Correct 360 ms 491128 KB Output is correct
4 Correct 351 ms 491128 KB Output is correct
5 Correct 353 ms 491128 KB Output is correct
6 Correct 349 ms 491128 KB Output is correct
7 Correct 348 ms 491128 KB Output is correct
8 Correct 340 ms 491128 KB Output is correct
9 Correct 341 ms 491128 KB Output is correct
10 Correct 338 ms 491128 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 349 ms 490600 KB Output is correct
3 Correct 343 ms 490656 KB Output is correct
4 Correct 363 ms 490676 KB Output is correct
5 Correct 351 ms 490936 KB Output is correct
6 Correct 340 ms 490968 KB Output is correct
7 Correct 349 ms 490988 KB Output is correct
8 Correct 334 ms 490988 KB Output is correct
9 Correct 340 ms 491068 KB Output is correct
10 Correct 381 ms 491100 KB Output is correct
11 Correct 344 ms 491100 KB Output is correct
12 Correct 346 ms 491128 KB Output is correct
13 Correct 360 ms 491128 KB Output is correct
14 Correct 351 ms 491128 KB Output is correct
15 Correct 353 ms 491128 KB Output is correct
16 Correct 349 ms 491128 KB Output is correct
17 Correct 348 ms 491128 KB Output is correct
18 Correct 340 ms 491128 KB Output is correct
19 Correct 341 ms 491128 KB Output is correct
20 Correct 338 ms 491128 KB Output is correct
21 Correct 486 ms 491128 KB Output is correct
22 Correct 1499 ms 491160 KB Output is correct
23 Correct 812 ms 491308 KB Output is correct
24 Correct 1301 ms 491308 KB Output is correct
25 Correct 854 ms 491404 KB Output is correct
26 Correct 1000 ms 491404 KB Output is correct
27 Execution timed out 2082 ms 491404 KB Time limit exceeded
28 Halted 0 ms 0 KB -