oj.uz

Submission #503076

# Submission time Handle Problem Language Result Execution time Memory
503076 2022-01-07T06:34:03 Z qwerasdfzxcl Skyscraper (JOI16_skyscraper) C++14
15 / 100
 3 ms 2252 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int MOD = 1e9+7;
int dp[101][101][3][1001], a[1001];

inline void add(int &x, int y){
    x += y;
    if (x>=MOD) x -= MOD;
}

int main(){
    int n, L;
    scanf("%d %d", &n, &L);
    for (int i=1;i<=n;i++) scanf("%d", a+i);
    sort(a+1, a+n+1);

    dp[n-1][0][1][(a[n]-a[n-1])] = 1;
    dp[n-1][0][2][(a[n]-a[n-1])*2] = 1;

    for (int i=n-2;i;i--){
        for (int j=0;j<=n;j++){
            int val0 = (a[i+1] - a[i]) * (j*2);
            int val1 = (a[i+1] - a[i]) * (j*2 + 1);
            int val2 = (a[i+1] - a[i]) * (j*2 + 2);

            if (j){
            for (int k=val0;k<=L;k++){
                add(dp[i][j][0][k], dp[i+1][j+1][0][k-val0] * (j+1) %MOD);
                add(dp[i][j][0][k], dp[i+1][j][0][k-val0] * (j*2) %MOD);
                add(dp[i][j][0][k], dp[i+1][j-1][0][k-val0] * (j-1) %MOD);

                add(dp[i][j][0][k], dp[i+1][j][1][k-val0] *2 %MOD);
                add(dp[i][j][0][k], dp[i+1][j-1][1][k-val0] *2 %MOD);
            }}

            for (int k=val1;k<=L;k++){
                add(dp[i][j][1][k], dp[i+1][j+1][1][k-val1] * (j+1) %MOD);
                add(dp[i][j][1][k], dp[i+1][j][1][k-val1] * (j*2+1) %MOD);
                if (j) add(dp[i][j][1][k], dp[i+1][j-1][1][k-val1] * j %MOD);

                add(dp[i][j][1][k], dp[i+1][j][2][k-val1]);
                if (j) add(dp[i][j][1][k], dp[i+1][j-1][2][k-val1]);
            }

            for (int k=val2;k<=L;k++){
                add(dp[i][j][2][k], dp[i+1][j+1][2][k-val2] * (j+1) %MOD);
                add(dp[i][j][2][k], dp[i+1][j][2][k-val2] * (j*2+2) %MOD);
                if (j) add(dp[i][j][2][k], dp[i+1][j-1][2][k-val2] * (j+1) %MOD);
            }
        }
    }

    int ans = 0;
    for (int k=0;k<=L;k++){
        add(ans, dp[1][1][0][k]);
        add(ans, dp[1][0][1][k]*2);

        //if (k<=10) printf("%d %d\n", dp[1][1][0][k], dp[1][0][1][k]);
    }

    printf("%d\n", ans);
    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1716 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 3 ms 2224 KB Output is correct
4 Correct 1 ms 1584 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1836 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 2244 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 2 ms 1688 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -