oj.uz

Submission #1094352

# Submission time Handle Problem Language Result Execution time Memory
1094352 2024-09-29T11:23:43 Z Mike_Vu Skyscraper (JOI16_skyscraper) C++14
20 / 100
 188 ms 260748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

namespace modulofunc{
    const int mod = 1e9+7;
    void ad(int &x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        x = temp;
    }
    int add(int x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        return temp;
    }
    int sub(int x, int y) {
        ll temp = x-y;
        if (temp < 0) temp += mod;
        return temp;
    }
    int mul(int x, int y) {
        return 1LL*x*y%mod;
    }
}
using namespace modulofunc;

const int maxn = 105, maxl = 1005;
int n, l, a[maxn];
int dp[maxn][maxn][maxl*2][3];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << 1;
        return 0;
    }
    sort(a+1, a+n+1);
    memset(dp, 0, sizeof(dp));
    dp[0][0][maxl][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int r = 0; r <= maxl+l; r++) {
                for (int k = 0; k < 3; k++) {
                    if (!dp[i][j][r][k]) continue;
                    //horizontal
                    //join
                    if (r+2*a[i+1] <= maxl+l && j > 1) ad(dp[i+1][j-1][r+2*a[i+1]][k], mul(dp[i][j][r][k], j-1));
                    //con
                    if (j > 0) ad(dp[i+1][j][r][k], mul(dp[i][j][r][k], 2*j-k));
                    //new
                    if (r-2*a[i+1] >= 0) ad(dp[i+1][j+1][r-2*a[i+1]][k], mul(dp[i][j][r][k], j+1-k));
                    //edge
                    if (k < 2) {
                        //con
                        if (r+a[i+1] <= maxl+l && j > 0) ad(dp[i+1][j][r+a[i+1]][k+1], mul(dp[i][j][r][k], 2-k));
                        //new
                        if (r-a[i+1] >= 0) ad(dp[i+1][j+1][r-a[i+1]][k+1], mul(dp[i][j][r][k], 2-k));
                    }
//                    cout << i << ' ' << j << ' ' << r << ' ' << r-maxl << ' ' << k << ' ' << dp[i][j][r][k] << "\n";
                }
            }
        }
    }
    int res = 0;
    for (int r = 0; r <= maxl+l; r++) {
        ad(res, dp[n][1][r][2]);
    }
    cout << res;
}
/*
4 10
3 6 2 9
8 35
3 7 1 5 10 2 11 6
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 106 ms 260540 KB Output is correct
3 Correct 107 ms 260436 KB Output is correct
4 Correct 110 ms 260432 KB Output is correct
5 Correct 109 ms 260432 KB Output is correct
6 Correct 108 ms 260436 KB Output is correct
7 Correct 112 ms 260432 KB Output is correct
8 Correct 116 ms 260436 KB Output is correct
9 Correct 126 ms 260436 KB Output is correct
10 Correct 123 ms 260436 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 260432 KB Output is correct
2 Correct 133 ms 260448 KB Output is correct
3 Correct 125 ms 260436 KB Output is correct
4 Correct 130 ms 260428 KB Output is correct
5 Correct 121 ms 260748 KB Output is correct
6 Correct 120 ms 260432 KB Output is correct
7 Correct 125 ms 260420 KB Output is correct
8 Correct 121 ms 260432 KB Output is correct
9 Correct 123 ms 260632 KB Output is correct
10 Correct 120 ms 260588 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 106 ms 260540 KB Output is correct
3 Correct 107 ms 260436 KB Output is correct
4 Correct 110 ms 260432 KB Output is correct
5 Correct 109 ms 260432 KB Output is correct
6 Correct 108 ms 260436 KB Output is correct
7 Correct 112 ms 260432 KB Output is correct
8 Correct 116 ms 260436 KB Output is correct
9 Correct 126 ms 260436 KB Output is correct
10 Correct 123 ms 260436 KB Output is correct
11 Correct 121 ms 260432 KB Output is correct
12 Correct 133 ms 260448 KB Output is correct
13 Correct 125 ms 260436 KB Output is correct
14 Correct 130 ms 260428 KB Output is correct
15 Correct 121 ms 260748 KB Output is correct
16 Correct 120 ms 260432 KB Output is correct
17 Correct 125 ms 260420 KB Output is correct
18 Correct 121 ms 260432 KB Output is correct
19 Correct 123 ms 260632 KB Output is correct
20 Correct 120 ms 260588 KB Output is correct
21 Correct 131 ms 260440 KB Output is correct
22 Incorrect 188 ms 260548 KB Output isn't correct
23 Halted 0 ms 0 KB -