oj.uz

Submission #551487

# Submission time Handle Problem Language Result Execution time Memory
551487 2022-04-20T20:34:41 Z leaked Skyscraper (JOI16_skyscraper) C++17
100 / 100
 358 ms 58316 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int M=1e9+7;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
const int N=200+2;
const int L=1'000+2;
int dp[N][N][L][2][2];
/// памяти пизда
/// i, todel_cnt,summod,wanttodel fi,wanttodel last
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    vec<int>a(n);
    for(auto &z : a)
        cin>>z;
    sort(all(a));
    for(int t=0;t<2;t++){
        int i=0;
        int d=(i+1<n?a[i+1]-a[i]:0);
        for(int t1=0;t1<2;t1++){
            if((t+t1)*d<=k)
                dp[i+1][0][d*(t+t1)][t][t1]=1;
        }
    }
//    vec<int> how(k+1,0);
//    auto check=[&](){
//        do{
//            int s=0;
//            for(int i=1;i<n;i++)
//                s+=abs(a[i]-a[i-1]);
//            if(s<=k)
//                how[s]++;
//        }while(next_permutation(all(a)));
//    };
//    check();
//    for(auto &z : a) cout<<z<<' ';
//    cout<<endl;
    for(int i=1;i<n;i++){
        int d=(i+1<n?a[i+1]-a[i]:0);

        for(int c=0;c<=i;c++){
            for(int s=0;s<=k;s++){
                /// one middle
                for(int t=0;t<2;t++){
                    for(int t1=0;t1<2;t1++){
                        if(c){
                            if(s+2*(c-1)*d+(t+t1)*d<=k)
                                add(dp[i+1][c-1][s+2*(c-1)*d+(t+t1)*d][t][t1],mult(c,dp[i][c][s][t][t1]));
                            if(s+2*(c)*d+(t+t1)*d<=k)
                                add(dp[i+1][c][s+2*(c)*d+(t+t1)*d][t][t1],mult(c,mult(2,dp[i][c][s][t][t1])));
                            if(s+2*(c+1)*d+(t+t1)*d<=k)
                                add(dp[i+1][c+1][s+2*(c+1)*d+(t+t1)*d][t][t1],mult(c,dp[i][c][s][t][t1]));
                        }
                    }
                }
                /// first
                for(int t1=0;t1<2;t1++){
                    int t=1;
                    if(s+2*c*d+(0+t1)*d<=k)
                        add(dp[i+1][c][s+2*c*d+(0+t1)*d][0][t1],dp[i][c][s][t][t1]);
                    if(s+2*c*d+(1+t1)*d<=k)
                        add(dp[i+1][c][s+2*c*d+(1+t1)*d][1][t1],dp[i][c][s][t][t1]);

                    if(s+2*(c+1)*d+(0+t1)*d<=k)
                        add(dp[i+1][c+1][s+2*(c+1)*d+(0+t1)*d][0][t1],dp[i][c][s][t][t1]);
                    if(s+2*(c+1)*d+(1+t1)*d<=k)
                        add(dp[i+1][c+1][s+2*(c+1)*d+(1+t1)*d][1][t1],dp[i][c][s][t][t1]);
                }
                /// last
                for(int t=0;t<2;t++){
                    int t1=1;

                    if(s+2*c*d+(0+t)*d<=k)
                        add(dp[i+1][c][s+2*c*d+(t+0)*d][t][0],dp[i][c][s][t][t1]);
                    if(s+2*c*d+(1+t)*d<=k)
                        add(dp[i+1][c][s+2*c*d+(t+1)*d][t][1],dp[i][c][s][t][t1]);

                    if(s+2*(c+1)*d+(0+t)*d<=k)
                        add(dp[i+1][c+1][s+2*(c+1)*d+(t+0)*d][t][0],dp[i][c][s][t][t1]);
                    if(s+2*(c+1)*d+(1+t)*d<=k)
                        add(dp[i+1][c+1][s+2*(c+1)*d+(t+1)*d][t][1],dp[i][c][s][t][t1]);
                }
            }
        }
//        cout<<dp[2][0][2][1][0]<<endl;
    }
    int ans=0;
    for(int s=0;s<=k;s++){
//        cout<<"S "<<s<<' '<<dp[n][0][s][0][0]<<' '<<how[s]<<endl;
        add(ans,dp[n][0][s][0][0]);
    }
    cout<<ans;
    return 0;
}
/*
5 14
3 7 1 5 10
1 3 5 7 10
11 2
aa
ab
aa
ca
aa
bc
ea
aa
ad
de
aa


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 840 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 724 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 840 KB Output is correct
16 Correct 2 ms 844 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 848 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 4 ms 3284 KB Output is correct
22 Correct 273 ms 49040 KB Output is correct
23 Correct 358 ms 56580 KB Output is correct
24 Correct 286 ms 58316 KB Output is correct
25 Correct 337 ms 56880 KB Output is correct
26 Correct 310 ms 54912 KB Output is correct
27 Correct 114 ms 35788 KB Output is correct
28 Correct 145 ms 40400 KB Output is correct
29 Correct 279 ms 57580 KB Output is correct
30 Correct 351 ms 57036 KB Output is correct