Submission #442063

#	Time	Username	Problem	Language	Result	Execution time	Memory
442063		JovanB	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	327 ms	2700 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1000000007;

int dp[105][1005][3];
int dpp[105][1005][3];
int a[105];

int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int mul(int a, int b){ return (1LL*a*b)%MOD; }

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, L;
    cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    if(n == 1){
        cout << "1\n";
        return 0;
    }
    if(2*(a[2]-a[1]) <= L) dp[1][2*(a[2]-a[1])][0] = 1;
    if(a[2] - a[1] <= L) dp[1][a[2]-a[1]][1] = 2;
    for(int i=2; i<=n; i++){
        int dif = a[i+1] - a[i];
        for(int j=1; j<=n; j++){
            for(int zb=0; zb<=L; zb++){
                for(int k=0; k<=2; k++){
                    dpp[j][zb][k] = dp[j][zb][k];
                    dp[j][zb][k] = 0;
                }
            }
        }
        for(int j=1; j<=n; j++){
            for(int zb=0; zb<=L; zb++){
                for(int k=0; k<=2; k++){
                    int val = dpp[j][zb][k];
                    /// povezujem 2 komponente
                    int posle = zb + dif*(2*j-k-2);
                    if(posle >= 0 && posle <= L) dp[j-1][posle][k] = add(dp[j-1][posle][k], mul(j-1, val));
                    /// uz jednu, ne stvaram endpoint
                    posle = zb + dif*(2*j-k);
                    if(posle >= 0 && posle <= L) dp[j][posle][k] = add(dp[j][posle][k], mul(2*j-k, val));
                    /// uz jednu, stvaram endpoint
                    posle = zb + dif*(2*j-k-1);
                    if(posle >= 0 && posle <= L && k < 2) dp[j][posle][k+1] = add(dp[j][posle][k+1], mul(2-k, val));
                    /// ni uz jednu, ne stvaram endpoint
                    posle = zb + dif*(2*j-k+2);
                    if(posle >= 0 && posle <= L) dp[j+1][posle][k] = add(dp[j+1][posle][k], mul(j+1-k, val));
                    /// ni uz jednu, stvaram endpoint
                    posle = zb + dif*(2*j-k+1);
                    if(posle >= 0 && posle <= L && k < 2) dp[j+1][posle][k+1] = add(dp[j+1][posle][k+1], mul(2-k, val));
                }
            }
        }
    }
    int res = 0;
    for(int i=0; i<=L; i++) res = add(res, dp[1][i][2]);
    cout << res << "\n";
    return 0;
}

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