oj.uz

Submission #1074392

# Submission time Handle Problem Language Result Execution time Memory
1074392 2024-08-25T10:15:52 Z steveonalex Skyscraper (JOI16_skyscraper) C++17
100 / 100
 183 ms 347372 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }


 
const int MOD = 1e9 + 7;
struct Modular{
    ll x;
    Modular(ll _x = 0){x = _x;}
    Modular& operator += (Modular y){
        x += y.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Modular operator + (Modular y) {
        Modular tmp = *this;
        return tmp += y;
    }
 
    Modular& operator -= (Modular y){
        x -= y.x;
        if (x < 0) x += MOD;
        return *this;
    }
    Modular operator - (Modular y) {
        Modular tmp = *this;
        return tmp -= y;
    }
 
    Modular& operator *= (Modular y){
        x *= y.x;
        if (x >= MOD) x %= MOD;
        return *this;
    }
    Modular operator * (Modular y) {
        Modular tmp = *this;
        return tmp *= y;
    }
 
    // use at your own risk
    bool operator == (Modular y){
        return x == y.x;
    }
    bool operator != (Modular y){
        return x != y.x;
    }
};
ostream& operator << (ostream& out, Modular x){
    out << x.x;
    return out;
}

const int N = 105, L = 1005;
Modular dp[N][N][L][4];
 
int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    clock_t start = clock();
 
    int n, l; cin >> n >> l;
    vector<int> a(n);
    for(int i = 0; i<n; ++i) cin >> a[i];

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

    sort(ALL(a));

    dp[0][1][0][0] = dp[0][1][0][1] = dp[0][1][0][2] = 1;
    for(int i = 1; i<n; ++i){
        int diff = a[i] - a[i-1];
        for(int j = 1; j <= n; ++j) for(int k = 0; k <= l; ++k) for(int x = 0; x < 4; ++x) if (dp[0][j][k][x] != 0){
            Modular cur = dp[0][j][k][x];
            int _k = k + diff * (j * 2 - pop_cnt(x));
            // add another connected component
            for(int y = -1; y<=1; ++y){
                if (y >= 0 && GETBIT(x, y)) continue;
                int _x = x;
                if (y >= 0) _x += MASK(y);
                Modular next_val = cur;
                if (y == -1) next_val *= (j+1-pop_cnt(x));
                if (_k <= l) dp[1][j+1][_k][_x] += next_val;
            }

            // add to the front or back of an existing component
            for(int y = -1; y<=1; ++y){
                if (y >= 0 && GETBIT(x, y)) continue;
                int _x = x;
                if (y >= 0) _x += MASK(y);
                Modular next_val = cur;
                if (y == -1) next_val *= (j*2-pop_cnt(x));
                if (_k <= l) dp[1][j][_k][_x] += next_val;
            }


            // joining two components
            Modular next_val = cur;
            next_val *= (j-1);
            if (_k <= l) dp[1][j-1][_k][x] += next_val;

            // if (i == 2 && j == 2 && k == 1 && x == 3) {
            //     cout << cur << "\n";
            //     cout << "> " << i+1 << " " << j << " " << _k << " " << x << "\n";
            // }
        }
        for(int j = 0; j <= n; ++j) for(int k = 0; k <= l; ++k) for(int x = 0; x < 4; ++x){
            // if (dp[1][j][k][x] != 0) cout << i + 1 << " " << j << " " << k << " " << x << " " << dp[1][j][k][x] << "\n";
            dp[0][j][k][x] = dp[1][j][k][x];
            dp[1][j][k][x] = 0;
        }
    }

    Modular ans = 0;
    for(int k = 0; k <= l; ++k) ans += dp[0][1][k][3];

    cout << ans << "\n";
 
    cerr << "Time elapsed: " << clock() - start << " ms\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 347220 KB Output is correct
2 Correct 129 ms 347220 KB Output is correct
3 Correct 133 ms 347296 KB Output is correct
4 Correct 122 ms 347220 KB Output is correct
5 Correct 119 ms 347128 KB Output is correct
6 Correct 138 ms 347336 KB Output is correct
7 Correct 123 ms 347216 KB Output is correct
8 Correct 109 ms 347220 KB Output is correct
9 Correct 128 ms 347364 KB Output is correct
10 Correct 136 ms 347172 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 347216 KB Output is correct
2 Correct 117 ms 347280 KB Output is correct
3 Correct 120 ms 347268 KB Output is correct
4 Correct 120 ms 347252 KB Output is correct
5 Correct 119 ms 347364 KB Output is correct
6 Correct 123 ms 347324 KB Output is correct
7 Correct 110 ms 347180 KB Output is correct
8 Correct 108 ms 347364 KB Output is correct
9 Correct 121 ms 347304 KB Output is correct
10 Correct 137 ms 347148 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 347220 KB Output is correct
2 Correct 129 ms 347220 KB Output is correct
3 Correct 133 ms 347296 KB Output is correct
4 Correct 122 ms 347220 KB Output is correct
5 Correct 119 ms 347128 KB Output is correct
6 Correct 138 ms 347336 KB Output is correct
7 Correct 123 ms 347216 KB Output is correct
8 Correct 109 ms 347220 KB Output is correct
9 Correct 128 ms 347364 KB Output is correct
10 Correct 136 ms 347172 KB Output is correct
11 Correct 155 ms 347216 KB Output is correct
12 Correct 117 ms 347280 KB Output is correct
13 Correct 120 ms 347268 KB Output is correct
14 Correct 120 ms 347252 KB Output is correct
15 Correct 119 ms 347364 KB Output is correct
16 Correct 123 ms 347324 KB Output is correct
17 Correct 110 ms 347180 KB Output is correct
18 Correct 108 ms 347364 KB Output is correct
19 Correct 121 ms 347304 KB Output is correct
20 Correct 137 ms 347148 KB Output is correct
21 Correct 121 ms 347132 KB Output is correct
22 Correct 177 ms 347188 KB Output is correct
23 Correct 170 ms 347220 KB Output is correct
24 Correct 179 ms 347356 KB Output is correct
25 Correct 183 ms 347220 KB Output is correct
26 Correct 148 ms 347216 KB Output is correct
27 Correct 143 ms 347216 KB Output is correct
28 Correct 141 ms 347324 KB Output is correct
29 Correct 159 ms 347216 KB Output is correct
30 Correct 164 ms 347372 KB Output is correct