oj.uz

Submission #1010330

# Submission time Handle Problem Language Result Execution time Memory
1010330 2024-06-28T19:44:17 Z tvladm2009 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 4 ms 3932 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 100 + 7;
const int L = 1000 + 7; 
const int M = 1e9 + 7;

int n, l, a[N];
int dp[N][N][L][2][2];

int add(int a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
    return a;
}

void addup(int &a, int b) {
    a = add(a, b);
}

int mul(int a, int b) {
    return (ll) a * b % M;
}

int mul(int a, int b, int c) {
    return mul(a, mul(b, c));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> l;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    dp[1][0][0][0][0] = 1;
    dp[1][0][0][0][1] = 1;
    dp[1][0][0][1][0] = 1;
    dp[1][0][0][1][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int s = 0; s <= l; ++s) {
                for (int S = 0; S <= 1; ++S) {
                    for (int F = 0; F <= 1; ++F) {
                        if (j > 0) { 
                            addup(dp[i + 1][j - 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][F], mul(dp[i][j][s][S][F], j));
                        }
                        addup(dp[i + 1][j][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][F], mul(dp[i][j][s][S][F], j, 2));
                        addup(dp[i + 1][j + 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][F], mul(dp[i][j][s][S][F], j));
                    
                        if (S == 1) {
                            addup(dp[i + 1][j + 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][0][F], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j + 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][1][F], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j][s + (2 * j + S + F) * (a[i + 1] - a[i])][0][F], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j][s + (2 * j + S + F) * (a[i + 1] - a[i])][1][F], dp[i][j][s][S][F]);
                        }
                        
                        if (F == 1) {
                            addup(dp[i + 1][j + 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][0], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j + 1][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][1], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][0], dp[i][j][s][S][F]);
                            addup(dp[i + 1][j][s + (2 * j + S + F) * (a[i + 1] - a[i])][S][1], dp[i][j][s][S][F]);
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= l; ++i) ans = add(ans, dp[n][0][i][0][0]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2516 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 4 ms 3932 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3928 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 2 ms 3532 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2516 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 4 ms 3932 KB Output isn't correct
6 Halted 0 ms 0 KB -