oj.uz

Submission #287980

# Submission time Handle Problem Language Result Execution time Memory
287980 2020-09-01T07:26:51 Z 반딧불(#5783) Skyscraper (JOI16_skyscraper) C++17
0 / 100
 1 ms 672 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n, l;
int arr[102];
ll DP[102][102][1002][4];
ll ans;

inline void update(int i, int j, int k, int b, ll val){
    if(1<=i && i<=n && 0<=j && j<=n && k<=l) DP[i][j][k][b] = (DP[i][j][k][b] + val) % MOD;
}

int main(){
    scanf("%d %d", &n, &l);
    if(n==1){
        printf("1");
        return 0;
    }

    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    sort(arr+1, arr+n+1);

    DP[1][1][0][0] = 1;
    DP[1][0][0][1] = 1;
    DP[1][0][0][2] = 1;

    for(int i=1; i<n; i++){
        for(int j=0; j<=i; j++){
            for(int k=0; k<=l; k++){
                for(int b=0; b<4; b++){
                    /// Place in the middle
                    int sideNum = 2*j + __builtin_popcount(b);
                    int val = k+sideNum*(arr[i+1] - arr[i]);
                    ll v = DP[i][j][k][b];
                    if(!v) continue;
                    if(i==n-1){
                        if(b==3 && j==0){
                            update(i+1, 0, k, b, v);
                        }
                        else if((b==1 || b==2) && j==0){
                            update(i+1, 0, k, b, v);
                        }
                        else continue;
                    }

                    /// Case #1. This connects two components
                    update(i+1, j-1, val, b, v*(j-1+__builtin_popcount(b)));
                    /// Case #2. This does not change the number of coponents
                    update(i+1, j, val, b, v*sideNum);
                    /// Case #3. This is not connected by any other numbers
                    update(i+1, j+1, val, b, v*(j+1));

                    /// Place in the left
                    if(b==0 || b==2){ /// nothing is in the left
                        update(i+1, j, val, b|1, v);
                    }
                    /// Place in the right
                    if(b==0 || b==1){ /// nothing is in the right
                        update(i+1, j, val, b|2, v);
                    }
                }
            }
        }
    }

//    for(int i=1; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=l; k++) for(int b=0; b<4; b++){
//        printf("%d %d %d %d -> %lld\n", i, j, k, b, DP[i][j][k][b]);
//    }

    for(int i=0; i<=l; i++){
        ans += DP[n][0][i][3];
        ans %= MOD;
    }
    printf("%lld", ans);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     scanf("%d %d", &n, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -