Submission #706299

#	Time	Username	Problem	Language	Result	Execution time	Memory
706299		ByeWorld	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	7 ms	3404 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O1")
#define int long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int MAXN = 110;
const double SMALL = 1e-6;
const int INF = 5e5+10;
const int MX = 2e12;
const int MOD = 1e9+7;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int sum(int a, int b){
    return (a+b)%MOD;
}
int sub(int a, int b){
    return (a+MOD-b)%MOD;
}
int mul(int a, int b){
    return (a*b)%MOD;
}

int dp[110][110][1010][4]; // dp[id][cc][sum][co]
int a[110];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, L; cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    
    dp[1][1][0][0] = 1; dp[1][1][0][1] = 2; dp[1][1][0][2] = 1;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<=L; k++){
                for(int co=0; co<=2; co++){
                    int dif = a[i+1]-a[i]; int te = k + dif*(2*j-co); 
                    // O+O j-1
                    dp[i+1][j-1][te][co] = sum(mul(j-1, dp[i][j][k][co]), dp[i+1][j-1][te][co]);
                    
                    // O+ 2j-co
                    dp[i+1][j][te][co] = sum(mul(2*j-co, dp[i][j][k][co]), dp[i+1][j][te][co]);
                    
                    // O+| 2-co 
                    dp[i+1][j][te][co+1] = sum(mul(2-co, dp[i][j][k][co]), dp[i+1][j][te][co+1]);
                    
                    // + j+1-co
                    dp[i+1][j+1][te][co] = sum(mul(j+1-co, dp[i][j][k][co]), dp[i+1][j+1][te][co]);
                    
                    // +| 2-co
                    dp[i+1][j+1][te][co+1] = sum(mul(2-co, dp[i][j][k][co]), dp[i+1][j+1][te][co+1]);
                    
                    //if(dp[i][j][k][co] != 0){
                    //    cout << i << ' ' << j <<  ' '<< k << ' ' << co << ' '<< dp[i][j][k][co]<<'\n';
                    //}
                }
            }
        }
    }
    
    int ans = 0;
    for(int i=0; i<=L; i++) ans = sum(ans, dp[n][1][i][2]);
    cout << ans << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80