oj.uz

Submission #389926

# Submission time Handle Problem Language Result Execution time Memory
389926 2021-04-14T21:23:57 Z smax Skyscraper (JOI16_skyscraper) C++17
100 / 100
 351 ms 260596 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template <typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

template<int MOD>
struct ModInt {
    long long v;
    ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
    ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
    ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
    ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
    ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
    bool operator == (const ModInt &other) const {return v == other.v;}
    bool operator != (const ModInt &other) const {return v != other.v;}
    friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
    friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
    friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
    friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
    friend ModInt operator - (const ModInt &a) {return 0 - a;}
    friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
    friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
    friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
};
typedef ModInt<1000000007> M;

// number of placed values, number of components, sum of abs(f_i - f_{i+1}), number of end gaps filled
M dp[105][105][1005][3];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, l;
    cin >> n >> l;
    vector<int> a(n + 1);
    for (int i=0; i<n; i++)
        cin >> a[i];
    a[n] = 1e4;

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

    sort(a.begin(), a.end());
    // form new individual component, joined to one of ends
    if (a[1] - a[0] <= l)
        dp[1][1][a[1] - a[0]][1] = 2;
    // form new individual component, not joined to end
    if (2 * (a[1] - a[0]) <= l)
        dp[1][1][2 * (a[1] - a[0])][0] = 1;
    for (int i=1; i<n; i++)
        for (int j=1; j<=i; j++)
            for (int k=0; k<=l; k++)
                for (int m=0; m<3; m++) {
                    int diff = a[i+1] - a[i];
                    // joined to one of ends
                    if (m < 2 && k + (2 * j - m + 1) * diff <= l)
                        dp[i+1][j+1][k+(2*j-m+1)*diff][m+1] += dp[i][j][k][m] * (2 - m);
                    // joined to an existing component
                    if (k + (2 * j - m) * diff <= l)
                        dp[i+1][j][k+(2*j-m)*diff][m] += dp[i][j][k][m] * (2 * j - m);
                    // merge two existing components together
                    if (j > 1 && k + (2 * (j - 1) - m) * diff <= l)
                        dp[i+1][j-1][k+(2*(j-1)-m)*diff][m] += dp[i][j][k][m] * (j - 1);
                    // merge a component with an end
                    if (m < 2 && k + (2 * j - m - 1) * diff <= l)
                        dp[i+1][j][k+(2*j-m-1)*diff][m+1] += dp[i][j][k][m] * (2 - m);
                    // not joined to anything
                    if (k + (2 * (j + 1) - m) * diff <= l)
                        dp[i+1][j+1][k+(2*(j+1)-m)*diff][m] += dp[i][j][k][m] * (j + 1 - m);
                }

    M ret = 0;
    for (int k=0; k<=l; k++)
        ret += dp[n][1][k][2];
    cout << ret << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 260472 KB Output is correct
2 Correct 142 ms 260404 KB Output is correct
3 Correct 144 ms 260596 KB Output is correct
4 Correct 139 ms 260444 KB Output is correct
5 Correct 147 ms 260436 KB Output is correct
6 Correct 140 ms 260488 KB Output is correct
7 Correct 143 ms 260416 KB Output is correct
8 Correct 137 ms 260404 KB Output is correct
9 Correct 149 ms 260420 KB Output is correct
10 Correct 137 ms 260548 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 260404 KB Output is correct
2 Correct 138 ms 260420 KB Output is correct
3 Correct 137 ms 260424 KB Output is correct
4 Correct 143 ms 260412 KB Output is correct
5 Correct 136 ms 260464 KB Output is correct
6 Correct 137 ms 260388 KB Output is correct
7 Correct 138 ms 260484 KB Output is correct
8 Correct 140 ms 260416 KB Output is correct
9 Correct 140 ms 260412 KB Output is correct
10 Correct 143 ms 260488 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 260472 KB Output is correct
2 Correct 142 ms 260404 KB Output is correct
3 Correct 144 ms 260596 KB Output is correct
4 Correct 139 ms 260444 KB Output is correct
5 Correct 147 ms 260436 KB Output is correct
6 Correct 140 ms 260488 KB Output is correct
7 Correct 143 ms 260416 KB Output is correct
8 Correct 137 ms 260404 KB Output is correct
9 Correct 149 ms 260420 KB Output is correct
10 Correct 137 ms 260548 KB Output is correct
11 Correct 144 ms 260404 KB Output is correct
12 Correct 138 ms 260420 KB Output is correct
13 Correct 137 ms 260424 KB Output is correct
14 Correct 143 ms 260412 KB Output is correct
15 Correct 136 ms 260464 KB Output is correct
16 Correct 137 ms 260388 KB Output is correct
17 Correct 138 ms 260484 KB Output is correct
18 Correct 140 ms 260416 KB Output is correct
19 Correct 140 ms 260412 KB Output is correct
20 Correct 143 ms 260488 KB Output is correct
21 Correct 139 ms 260384 KB Output is correct
22 Correct 307 ms 260572 KB Output is correct
23 Correct 346 ms 260496 KB Output is correct
24 Correct 329 ms 260548 KB Output is correct
25 Correct 347 ms 260420 KB Output is correct
26 Correct 322 ms 260496 KB Output is correct
27 Correct 202 ms 260408 KB Output is correct
28 Correct 236 ms 260488 KB Output is correct
29 Correct 325 ms 260420 KB Output is correct
30 Correct 351 ms 260484 KB Output is correct