oj.uz

Submission #634532

# Submission time Handle Problem Language Result Execution time Memory
634532 2022-08-24T14:27:49 Z lethinh05 Skyscraper (JOI16_skyscraper) C++11
15 / 100
 1 ms 980 KB 
#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", 1;

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

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 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -