Submission #634533

#	Time	Username	Problem	Language	Result	Execution time	Memory
634533		lethinh05	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	166 ms	142720 KiB

skyscraper

#include <bits/stdc++.h>

#define oo 1000000007
#define ll long long
#define ld long double
#define ii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define mp make_pair
#define vi vector<int>
#define vii vector<ii>
#define isz(a) (int)(a.size())
#define pb push_back
#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define bug(x) "["#x" = "<<(x)<<"] "
#define maxN 105

using namespace std;

const int MOD = oo;

int n, L, a[maxN];
ll f[maxN][maxN][1005][6];

int main() {
    #ifdef LOCALME
        freopen("JOI16_skyscraper.INP", "r", stdin);
        freopen("JOI16_skyscraper.OUT", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> L;
    fto(i, 1, n) cin >> a[i];

    if (n == 1) return cout << "1\n", 0;

    sort(a+1, a+n+1);
    a[n+1] = 10000;

    //f[1][1][2*a[2] - 2*a[1]][0] = f[1][1][a[2] - a[1]][1] = 1;
    f[0][0][0][0] = 1;
    fto(i, 1, n) {
        fto(j, 1, i) {
            fto(k, 0, L) {
                fto(m, 0, 2) {
                    int delta = (2*j - m)*(a[i+1] - a[i]);
                    if (k < delta) continue;

                    f[i][j][k][m] = f[i-1][j][k - delta][m]*(2*j - m)%MOD;
                    f[i][j][k][m] = (f[i][j][k][m] + f[i-1][j-1][k - delta][m]*(j - m)) % MOD;
                    f[i][j][k][m] = (f[i][j][k][m] + f[i-1][j+1][k - delta][m]*j) % MOD;

                    if (m >= 1) {
                        f[i][j][k][m] = (f[i][j][k][m] + f[i-1][j][k - delta][m-1]*(3-m)) % MOD;
                        f[i][j][k][m] = (f[i][j][k][m] + f[i-1][j-1][k - delta][m-1]*(3-m)) % MOD;
                    }

//                    if (i == 2 && j == 1 && k == 4 && m == 1) {
//                        cerr << f[i-1][j][k - (2*j - m)*(a[i+1] - a[i])][m]*(2*j - m) << "\n"
//                            << f[i-1][j-1][k + (2*(j-1) - m)*a[i] - (2*j - m)*a[i+1] + 2*a[i]][m]*(j - m) << "\n"
//                            << f[i-1][j+1][k + (2*(j+1) - m)*a[i] - (2*j - m)*a[i+1] - 2*a[i]][m]*j << "\n"
//                            << f[i-1][j][k + (2*j - (m-1))*a[i] - (2*j - m)*a[i+1] - a[i]][m-1]*(3-m) << "\n"
//                            << f[i-1][j-1][k + (2*(j-1) - (m-1))*a[i] - (2*j - m)*a[i+1] + a[i]][m-1]*(3-m) << "\n";
//                    }
//
//                    if (f[i][j][k][m] != 0) cerr << bug(i) << bug(j) << bug(k) << bug(m) << bug(f[i][j][k][m]) << "\n";
                }
            }
        }
    }

    int ans = 0;
    fto(i, 1, L) ans = (ans + f[n][1][i][2]) % MOD;
    cout << ans << "\n";
    return 0;
}

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