oj.uz

Submission #901442

# Submission time Handle Problem Language Result Execution time Memory
901442 2024-01-09T12:32:31 Z warner1129 Skyscraper (JOI16_skyscraper) C++17
20 / 100
 13 ms 3560 KB 
#include <bits/stdc++.h>
 
using namespace std;

 
#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
 
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
 
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
 
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

void solve() {
    int n, L;
    cin >> n >> L;

    vector<int> A(n);
    for (auto &x : A) cin >> x;

    sort(all(A));

    if (n == 1) {
        cout << 1 << '\n';
        return;
    }

    vector dp(n + 1, vector(3, vector<i64>(L + 1)));
    dp[1][0][0] = 1;
    dp[1][1][0] = 2;
    dp[1][2][0] = 1;

    for (int i = 1; i < n; i++) {
        vector f(n + 1, vector(3, vector<i64>(L + 1)));
        
        for (int j = 1; j <= i; j++)
            for (int k = 0; k <= 2; k++) {
                i64 w = (A[i] - A[i - 1]) * (j * 2 - k);
                
                for (int s = 0; s + w <= L; s++) if (dp[j][k][s]) {
                    i64 way = dp[j][k][s];
                    
                    f[j + 1][k][s + w] += way * (j + 1 - k);
                    f[j][k][s + w] += way * (j * 2 - k);
                    f[j - 1][k][s + w] += way * (j - 1);
                    
                    if (k == 0) {
                        f[j + 1][k + 1][s + w] += way * 2;
                        f[j][k + 1][s + w] += way * 2;
                    }
                    if (k == 1) {
                        f[j + 1][k + 1][s + w] += way;
                        f[j][k + 1][s + w] += way;
                    }
                }
            }
            
        dp.swap(f);
    }

    i64 ans = 0;
    for (int i = 0; i <= L; i++)
        (ans += dp[1][2][i]) %= mod;

    cout << ans << '\n';
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 13 ms 3560 KB Output isn't correct
23 Halted 0 ms 0 KB -