oj.uz

Submission #431969

# Submission time Handle Problem Language Result Execution time Memory
431969 2021-06-17T17:50:21 Z MarcoMeijer Skyscraper (JOI16_skyscraper) C++14
100 / 100
 424 ms 312900 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 

// mod library
ll MOD=1e9+7;

inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return mod(value+rs);}
    mi  operator- (ll rs) {return mod(value-rs+MOD);}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}

    ll value;
};
typedef vector<mi> vmi;

//===================//
//   begin program   //
//===================//
 
const int MX = 110;
const int N = (1<<20);

int n, l, a[MX];
mi dp[MX][MX][MX*10][3];

void program() {
    IN(n,l);
    if(n == 1) return OUTL(1);
    RE1(i,n) IN(a[i]);
    sort(a+1,a+n+1);
    a[n+1] = 1e4;
    dp[0][0][0][0] = 1;
    RE1(i,n) { // first i buildings
        RE1(j,i) { // j components
            RE(k,l+1) { // total cost
                RE(m,3) { // m end points so far
                    int delta = (2*j - m)*(a[i+1]-a[i]);
                    if(delta > k || i + j + 1 - m > n) continue;

                    mi res = 0;

                    // create new component
                    res += dp[i-1][j-1][k - delta][m];

                    // create now component on endpoint
                    if(m) res += mi(3-m)*dp[i-1][j-1][k - delta][m-1];

                    // append to existing component
                    res += mi(2*j - m)*dp[i-1][j][k-delta][m];

                    // append to existing component on endpoint
                    if(m == 1) res += mi(2*j)*dp[i-1][j][k - delta][m-1];
                    if(m == 2) {
                        if(i == n) res += dp[i-1][j][k - delta][m-1];
                        else if(j > 1) res += mi(j - 1)*dp[i-1][j][k - delta][m-1];
                    }

                    // join two existing components
                    if(m == 2) {
                        if(i == n) res += dp[i-1][j+1][k - delta][m];
                        else res += mi(j)*mi(j-1)*dp[i-1][j+1][k - delta][m];
                    }
                    else if(m == 1) res += mi(j)*mi(j)*dp[i-1][j+1][k - delta][m];
                    else res += mi(j)*mi(j+1)*dp[i-1][j+1][k - delta][m];

                    dp[i][j][k][m] = res;
                }
            }
        }
    }

    mi ans = 0;
    RE(k,l+1) ans += dp[n][1][k][2];
    OUTL(ll(ans));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 312852 KB Output is correct
2 Correct 169 ms 312844 KB Output is correct
3 Correct 164 ms 312900 KB Output is correct
4 Correct 174 ms 312740 KB Output is correct
5 Correct 167 ms 312808 KB Output is correct
6 Correct 172 ms 312796 KB Output is correct
7 Correct 176 ms 312772 KB Output is correct
8 Correct 163 ms 312748 KB Output is correct
9 Correct 171 ms 312772 KB Output is correct
10 Correct 159 ms 312836 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 312780 KB Output is correct
2 Correct 169 ms 312864 KB Output is correct
3 Correct 165 ms 312744 KB Output is correct
4 Correct 167 ms 312828 KB Output is correct
5 Correct 164 ms 312852 KB Output is correct
6 Correct 165 ms 312772 KB Output is correct
7 Correct 165 ms 312800 KB Output is correct
8 Correct 169 ms 312900 KB Output is correct
9 Correct 169 ms 312900 KB Output is correct
10 Correct 166 ms 312792 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 312852 KB Output is correct
2 Correct 169 ms 312844 KB Output is correct
3 Correct 164 ms 312900 KB Output is correct
4 Correct 174 ms 312740 KB Output is correct
5 Correct 167 ms 312808 KB Output is correct
6 Correct 172 ms 312796 KB Output is correct
7 Correct 176 ms 312772 KB Output is correct
8 Correct 163 ms 312748 KB Output is correct
9 Correct 171 ms 312772 KB Output is correct
10 Correct 159 ms 312836 KB Output is correct
11 Correct 168 ms 312780 KB Output is correct
12 Correct 169 ms 312864 KB Output is correct
13 Correct 165 ms 312744 KB Output is correct
14 Correct 167 ms 312828 KB Output is correct
15 Correct 164 ms 312852 KB Output is correct
16 Correct 165 ms 312772 KB Output is correct
17 Correct 165 ms 312800 KB Output is correct
18 Correct 169 ms 312900 KB Output is correct
19 Correct 169 ms 312900 KB Output is correct
20 Correct 166 ms 312792 KB Output is correct
21 Correct 167 ms 312828 KB Output is correct
22 Correct 334 ms 312796 KB Output is correct
23 Correct 405 ms 312900 KB Output is correct
24 Correct 395 ms 312772 KB Output is correct
25 Correct 423 ms 312772 KB Output is correct
26 Correct 377 ms 312860 KB Output is correct
27 Correct 243 ms 312772 KB Output is correct
28 Correct 259 ms 312860 KB Output is correct
29 Correct 358 ms 312768 KB Output is correct
30 Correct 424 ms 312860 KB Output is correct