oj.uz

Submission #202825

# Submission time Handle Problem Language Result Execution time Memory
202825 2020-02-18T05:25:55 Z tri Skyscraper (JOI16_skyscraper) C++14
100 / 100
 1809 ms 51064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const ll MOD = 1e9 + 7;
const int MAXC = 8001;

ll cDP[101][MAXC][4];
ll nDP[101][MAXC][4];

int h[105];

int main() {
    int N, L;
    cin >> N >> L;

    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }

    for (int i = 1; i <= N; i++) {
        cin >> h[i];
    }

    sort(h + 1, h + N + 1);
    reverse(h + 1, h + N + 1);

//    for (int i = 1; i <= N; i++) {
//        ps(h[i]);
//    }

    //number of components, cost, type (bitmask for whether or not we've already selected left/right ends)

    memset(cDP, 0, sizeof(cDP));
    cDP[0][0][0] = 1; // 1 way to have no components, no cost, and no endpoints at beginning

    for (int i = 0; i < N; i++) { // push transitions
        memset(nDP, 0, sizeof(nDP));
        for (int cComp = 0; cComp <= 100; cComp++) {
            for (int cCost = 0; cCost < MAXC; cCost++) {
                for (int cType = 0; cType < 4; cType++) { //typing stores status of left and right ends
                    if (cDP[cComp][cCost][cType] == 0) continue;

//                    ps("pushing", i, cComp, cCost, cType);

                    ll cCnt = cDP[cComp][cCost][cType];
                    int nFixed = ((cType & 0b10) != 0) + ((cType & 1) != 0);

                    // same type

                    // case: new component, it will be greater than all later so height will be added twice
                    int nCost = cCost + 2 * h[i + 1];
                    if (nCost < MAXC) {
                        // number of places we can put it is cComp + 1 - number of already fixed sides
                        nDP[cComp + 1][nCost][cType] =
                                (nDP[cComp + 1][nCost][cType] + cCnt * (cComp + 1 - nFixed)) % MOD;
                    }

                    // case: add to 1 component, less than attached but greater than later attached so net change is 0
                    if (cComp > 0) {
                        nCost = cCost;
                        // number of places we can attach it to is 2 * nComp - number of already fixed sides
                        nDP[cComp][nCost][cType] = (nDP[cComp][nCost][cType] + cCnt * (2 * cComp - nFixed)) % MOD;
                    }

                    // case: combine 2 components
                    if (cComp >= 2) {
                        nCost = cCost - 2 * h[i + 1]; // will be lower than both attached
                        assert(nCost >= 0);
                        // number of 2 components we can combine is cComp - 1
                        nDP[cComp - 1][nCost][cType] = (nDP[cComp - 1][nCost][cType] + cCnt * (cComp - 1)) % MOD;
                    }

                    // type change

                    for (int side = 1; side < 3; side++) {
                        if ((cType & side) == 0) {
                            int nType = cType | side;

                            // case: new component on left/right
                            nCost = cCost + h[i + 1];
                            if (nCost < MAXC) {
                                nDP[cComp + 1][nCost][nType] = (nDP[cComp + 1][nCost][nType] + cCnt) % MOD;
                            }

                            // case: attach to component on left/right
                            if (cComp > 0) {
                                nCost = cCost - h[i + 1];
                                assert(nCost >= 0);
                                nDP[cComp][nCost][nType] = (nDP[cComp][nCost][nType] + cCnt) % MOD;
                            }
                        }
                    }
                }
            }
        }
//        ps(i);
        memcpy(cDP, nDP, sizeof(nDP));
//        ps("finswap");
    }

    ll ans = 0;

    for (int cCost = 0; cCost <= L; cCost++) {
        ans = (ans + cDP[1][cCost][0b11]) % MOD;
    }

    cout << ans << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 55 ms 50936 KB Output is correct
3 Correct 64 ms 50936 KB Output is correct
4 Correct 103 ms 50936 KB Output is correct
5 Correct 117 ms 50936 KB Output is correct
6 Correct 121 ms 50936 KB Output is correct
7 Correct 128 ms 50936 KB Output is correct
8 Correct 119 ms 50936 KB Output is correct
9 Correct 119 ms 50936 KB Output is correct
10 Correct 117 ms 50936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 50960 KB Output is correct
2 Correct 194 ms 51064 KB Output is correct
3 Correct 182 ms 50936 KB Output is correct
4 Correct 189 ms 50940 KB Output is correct
5 Correct 186 ms 50936 KB Output is correct
6 Correct 185 ms 50936 KB Output is correct
7 Correct 190 ms 50940 KB Output is correct
8 Correct 183 ms 50936 KB Output is correct
9 Correct 188 ms 51064 KB Output is correct
10 Correct 191 ms 51064 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 55 ms 50936 KB Output is correct
3 Correct 64 ms 50936 KB Output is correct
4 Correct 103 ms 50936 KB Output is correct
5 Correct 117 ms 50936 KB Output is correct
6 Correct 121 ms 50936 KB Output is correct
7 Correct 128 ms 50936 KB Output is correct
8 Correct 119 ms 50936 KB Output is correct
9 Correct 119 ms 50936 KB Output is correct
10 Correct 117 ms 50936 KB Output is correct
11 Correct 168 ms 50960 KB Output is correct
12 Correct 194 ms 51064 KB Output is correct
13 Correct 182 ms 50936 KB Output is correct
14 Correct 189 ms 50940 KB Output is correct
15 Correct 186 ms 50936 KB Output is correct
16 Correct 185 ms 50936 KB Output is correct
17 Correct 190 ms 50940 KB Output is correct
18 Correct 183 ms 50936 KB Output is correct
19 Correct 188 ms 51064 KB Output is correct
20 Correct 191 ms 51064 KB Output is correct
21 Correct 510 ms 51064 KB Output is correct
22 Correct 1229 ms 51040 KB Output is correct
23 Correct 1310 ms 51064 KB Output is correct
24 Correct 1416 ms 51064 KB Output is correct
25 Correct 1331 ms 51064 KB Output is correct
26 Correct 1367 ms 51064 KB Output is correct
27 Correct 1797 ms 51064 KB Output is correct
28 Correct 1809 ms 51064 KB Output is correct
29 Correct 1743 ms 51064 KB Output is correct
30 Correct 1338 ms 50968 KB Output is correct