제출 #1191873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191873		SSKMF	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	39 ms	1608 KiB

skyscraper

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

const int mod(1000000007);
int sir[101] , modalitati[3][102][1001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , limita;
    cin >> lungime >> limita;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; }

    if (lungime == 1)
        { cout << '1'; return 0; }

    sort(sir + 1 , sir + lungime + 1);

    modalitati[0][1][0] = 1;
    modalitati[1][1][0] = 2;
    for (int maxim = 2 ; maxim <= lungime ; maxim++) {
        for (int suma = limita ; suma >= 0 ; suma--) {
            for (int componente = maxim ; componente ; componente--)
            {
                modalitati[2][componente][suma] = (
                    (componente > 1 && suma - (2 * (componente - 1) - 2) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * (componente - 2) * modalitati[2][componente - 1][suma - (2 * (componente - 1) - 2) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * componente - 2) * (sir[maxim] - sir[maxim - 1]) >= 0 ? (2LL * componente - 2) * modalitati[2][componente][suma - (2 * componente - 2) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * (componente + 1) - 2) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * componente * modalitati[2][componente + 1][suma - (2 * (componente + 1) - 2) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * (componente - 1) - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? modalitati[1][componente - 1][suma - (2 * (componente - 1) - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * componente - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? modalitati[1][componente][suma - (2 * componente - 1) * (sir[maxim] - sir[maxim - 1])] : 0)
                ) % mod;

                modalitati[1][componente][suma] = (
                    (suma - (2 * (componente - 1) - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * (componente - 1) * modalitati[1][componente - 1][suma - (2 * (componente - 1) - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * componente - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? (2LL * componente - 1) * modalitati[1][componente][suma - (2 * componente - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - (2 * (componente + 1) - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * componente * modalitati[1][componente + 1][suma - (2 * (componente + 1) - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    2LL * (
                        (suma - 2 * (componente - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? modalitati[0][componente - 1][suma - 2 * (componente - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                        (suma - 2 * componente * (sir[maxim] - sir[maxim - 1]) >= 0 ? modalitati[0][componente][suma - 2 * componente * (sir[maxim] - sir[maxim - 1])] : 0)
                        )
                ) % mod;

                modalitati[0][componente][suma] = (
                    (suma - 2 * (componente - 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * componente * modalitati[0][componente - 1][suma - 2 * (componente - 1) * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - 2 * componente * (sir[maxim] - sir[maxim - 1]) >= 0 ? 2LL * componente * modalitati[0][componente][suma - 2 * componente * (sir[maxim] - sir[maxim - 1])] : 0) +
                    (suma - 2 * (componente + 1) * (sir[maxim] - sir[maxim - 1]) >= 0 ? 1LL * componente * modalitati[0][componente + 1][suma - 2 * (componente + 1) * (sir[maxim] - sir[maxim - 1])] : 0)
                ) % mod;
            }
        }
    }

    int total = 0;
    for (int suma = 0 ; suma <= limita ; suma++) {
        if ((total += modalitati[2][1][suma]) >= mod)
            { total -= mod; }
    }

    cout << total;
    return 0;
}

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