oj.uz

Submission #982621

# Submission time Handle Problem Language Result Execution time Memory
982621 2024-05-14T14:00:32 Z dimashhh Skyscraper (JOI16_skyscraper) C++17
20 / 100
 2000 ms 263492 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e2 + 5, MOD = 1e9 + 7;

int n,l,a[N];
unordered_map<int,int> dp[N][N][2][2];
void add(int &x,int y){
    x += y;
    if(x >= MOD) x -= MOD;
}
void test(){
    cin >> n >> l;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    sort(a + 1,a + n + 1);
    if(n == 1) {
        cout << 1;
        return;
    }
    dp[2][1][0][0][(a[2]-a[1])*2] = 1;
    dp[2][1][0][1][a[2]-a[1]] = dp[2][1][1][0][a[2]-a[1]] = 1;
    a[n+1] = 10000;
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= i;j++){
            for(int s = 0;s < 2;s++){
                for(int t = 0;t < 2;t++){
                    for(auto [k,d]:dp[i][j][s][t]){
                        ll val = (a[i+1]-a[i]);
                        {//new
                            add(dp[i+1][j+1][s][t][k+val*((j+1)*2-s-t)],d*1ll*(j+1-s-t)%MOD);
                            if(!s){
                                add(dp[i+1][j+1][1][t][k+val*((j+1)*2-1-t)],d);
                            }
                            if(!t){
                                add(dp[i+1][j+1][s][1][k+val*((j+1)*2-1-s)],d);
                            }
                        }
                        {//merge
                            add(dp[i+1][j-1][s][t][k+val*((j-1)*2-s-t)],d*1ll*(j-1)%MOD);
                        }
                        {//corner
                            add(dp[i+1][j][s][t][k+val*(2*j-s-t)],d*1ll*(j*2-s-t)%MOD);
                            if(!s){
                                add(dp[i+1][j][1][t][k+val*(2*j-1-t)],d);
                            }
                            if(!t){
                                add(dp[i+1][j][s][1][k+val*(2*j-1-s)],d);
                            }
                        }
                    }
                }
            }
        }
        for(int j = 1;j <= i;j++){
            for(int s = 0;s < 2;s++){
                for(int t = 0;t < 2;t++){
                    dp[i][j][s][t].clear();
                }
            }
        }
    }
    int ans = 0;
    for(auto [x,y]:dp[n+1][1][1][1]){
        if(x <= l && x >= 0){
            add(ans,y);
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while (T--){
        test();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 4 ms 3932 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 11 ms 5976 KB Output is correct
3 Correct 3 ms 3420 KB Output is correct
4 Correct 11 ms 5980 KB Output is correct
5 Correct 17 ms 6748 KB Output is correct
6 Correct 7 ms 4700 KB Output is correct
7 Correct 5 ms 3808 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 3 ms 3636 KB Output is correct
10 Correct 9 ms 5468 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 4 ms 3932 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 11 ms 5976 KB Output is correct
13 Correct 3 ms 3420 KB Output is correct
14 Correct 11 ms 5980 KB Output is correct
15 Correct 17 ms 6748 KB Output is correct
16 Correct 7 ms 4700 KB Output is correct
17 Correct 5 ms 3808 KB Output is correct
18 Correct 3 ms 3420 KB Output is correct
19 Correct 3 ms 3636 KB Output is correct
20 Correct 9 ms 5468 KB Output is correct
21 Correct 121 ms 23640 KB Output is correct
22 Execution timed out 2068 ms 263492 KB Time limit exceeded
23 Halted 0 ms 0 KB -