oj.uz

Submission #1074398

# Submission time Handle Problem Language Result Execution time Memory
1074398 2024-08-25T10:16:49 Z steveonalex Skyscraper (JOI16_skyscraper) C++17
100 / 100
 196 ms 347308 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));
            if (_k > l) continue;
            // 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));
                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));
                dp[1][j][_k][_x] += next_val;
            }


            // joining two components
            Modular next_val = cur;
            next_val *= (j-1);
            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 115 ms 347264 KB Output is correct
2 Correct 113 ms 347216 KB Output is correct
3 Correct 115 ms 347220 KB Output is correct
4 Correct 111 ms 347308 KB Output is correct
5 Correct 116 ms 347216 KB Output is correct
6 Correct 116 ms 347232 KB Output is correct
7 Correct 110 ms 347216 KB Output is correct
8 Correct 133 ms 347216 KB Output is correct
9 Correct 128 ms 347216 KB Output is correct
10 Correct 111 ms 347220 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 347156 KB Output is correct
2 Correct 123 ms 347288 KB Output is correct
3 Correct 112 ms 347152 KB Output is correct
4 Correct 135 ms 347216 KB Output is correct
5 Correct 113 ms 347288 KB Output is correct
6 Correct 136 ms 347220 KB Output is correct
7 Correct 114 ms 347244 KB Output is correct
8 Correct 114 ms 347244 KB Output is correct
9 Correct 130 ms 347216 KB Output is correct
10 Correct 121 ms 347216 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 347264 KB Output is correct
2 Correct 113 ms 347216 KB Output is correct
3 Correct 115 ms 347220 KB Output is correct
4 Correct 111 ms 347308 KB Output is correct
5 Correct 116 ms 347216 KB Output is correct
6 Correct 116 ms 347232 KB Output is correct
7 Correct 110 ms 347216 KB Output is correct
8 Correct 133 ms 347216 KB Output is correct
9 Correct 128 ms 347216 KB Output is correct
10 Correct 111 ms 347220 KB Output is correct
11 Correct 114 ms 347156 KB Output is correct
12 Correct 123 ms 347288 KB Output is correct
13 Correct 112 ms 347152 KB Output is correct
14 Correct 135 ms 347216 KB Output is correct
15 Correct 113 ms 347288 KB Output is correct
16 Correct 136 ms 347220 KB Output is correct
17 Correct 114 ms 347244 KB Output is correct
18 Correct 114 ms 347244 KB Output is correct
19 Correct 130 ms 347216 KB Output is correct
20 Correct 121 ms 347216 KB Output is correct
21 Correct 109 ms 347280 KB Output is correct
22 Correct 196 ms 347216 KB Output is correct
23 Correct 182 ms 347216 KB Output is correct
24 Correct 180 ms 347136 KB Output is correct
25 Correct 181 ms 347188 KB Output is correct
26 Correct 172 ms 347220 KB Output is correct
27 Correct 135 ms 347148 KB Output is correct
28 Correct 156 ms 347220 KB Output is correct
29 Correct 175 ms 347216 KB Output is correct
30 Correct 189 ms 347216 KB Output is correct