oj.uz

Submission #911144

# Submission time Handle Problem Language Result Execution time Memory
911144 2024-01-18T13:37:43 Z Spade1 Skyscraper (JOI16_skyscraper) C++14
100 / 100
 365 ms 5212 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;

template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define rep0(a) for (ll i = 1; i <= a; ++i)
#define rep1(i, a) for (ll i = 1; i <= a; ++i)
#define rep2(i, a, b) for (ll i = a; i <= b; ++i)
#define rep3(i, a, b, c) for (ll i = a; i <= b; i+=c) 
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define repd0(a) for (ll i = a; i >= 1; --i)
#define repd1(i, a) for (ll i = a; i >= 1; --i)
#define repd2(i, a, b) for (ll i = b; i >= a; --i)
#define repd3(i, a, b, c) for (ll i = b; i >= a; i-=c)
#define repd(...) overload4(__VA_ARGS__, repd3, repd2, repd1, repd0)(__VA_ARGS__)
#define trav(a, x) for (auto& a : x)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert

template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const char nl = '\n';
const int MX = 110;

ll modmul(ll a,ll b,ll mod){
    ll res=(a*b-ll(1.l*a*b/mod)*mod)%mod;
    if(res<0)res+=mod;
    return res;
}
ll modinv(ll a, ll b) {
  ll x=0,x1=1;
  while(a!=0){
    ll q=b/a;
    b-=q*a; x-=q*x1;
    swap(a,b); swap(x,x1);
  }
  return x;
}
template<ll M>
struct Mint {
  ll x;
  constexpr Mint():x(0){}
  constexpr Mint(ll x):x(norm(x%getMod())){}
  static ll Mod;
  constexpr static ll getMod() {return M>0?M:Mod;}
  constexpr static void setMod(ll Mod_) {Mod=Mod_;}
  constexpr ll norm(ll x) const {if(x<0)x+=getMod(); if(x>=getMod())x-=getMod(); return x;}
  explicit constexpr operator ll()const{return x;}
  constexpr Mint operator-()const {Mint res; res.x=norm(-x); return res;}
  constexpr Mint inv()const{return modinv(x, getMod());}
  constexpr Mint &operator+=(const Mint &rhs) {x=norm(x+rhs.x); return *this;}
  constexpr Mint &operator-=(const Mint &rhs) {x=norm(x-rhs.x); return *this;}
  constexpr Mint &operator*=(const Mint &rhs) {x=modmul(x, rhs.x, getMod()); return *this;}
  constexpr Mint &operator/=(const Mint &rhs) {x=modmul(x, rhs.inv().x, getMod()); return *this;}
  constexpr Mint &operator++(){return *this+=1;}
  constexpr Mint &operator--(){return *this-=1;}
  constexpr Mint operator++(int) {Mint res=*this; *this+=1; return res;}
  constexpr Mint operator--(int) {Mint res=*this; *this-=1; return res;}
  friend constexpr Mint operator+(Mint lhs, const Mint &rhs) {return lhs+=rhs;}
  friend constexpr Mint operator-(Mint lhs, const Mint &rhs) {return lhs-=rhs;}
  friend constexpr Mint operator*(Mint lhs, const Mint &rhs) {return lhs*=rhs;}
  friend constexpr Mint operator/(Mint lhs, const Mint &rhs) {return lhs/=rhs;} 
  friend istream &operator>>(istream &is, Mint &o) {ll x{}; is>>x; o=Mint(x); return is;}
  friend ostream &operator<<(ostream &os, const Mint &o) {return os<<o.x;}
  friend constexpr bool operator==(const Mint &lhs, const Mint &rhs) {return lhs.x==rhs.x;}
  friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs) {return lhs.x!=rhs.x;}
  friend constexpr bool operator<(const Mint &lhs, const Mint &rhs) {return lhs.x<rhs.x;}
};
template<>
ll Mint<0ll>::Mod=ll(1e18)+9;
using mint = Mint<MOD>;
using vm = vector<mint>;

int a[MX];
mint dp[MX][1002][3], tmp[MX][1002][3];

void solve() {
  int n, l; cin >> n >> l;
  rep(i, 1, n) cin >> a[i];
  sort(a+1, a+n+1);
  if (n==1) cout << 1 << nl, exit(0);
  tmp[1][0][0] = tmp[1][0][1] = 1;
  rep(i, 2, n) {
    rep(j, 1, n) {
      rep(k, 0, l) {
        rep(e, 0, 2) {
          int val = k + (2*j-e)*(a[i]-a[i-1]);
          if (val > l) continue;
          dp[j+1][val][e] += (j-e+1)*tmp[j][k][e];
          dp[j][val][e] += (2*j-e)*tmp[j][k][e];
          dp[j-1][val][e] += (j-1)*tmp[j][k][e];
          if (e > 1) continue;
          dp[j+1][val][e+1] += (1+e)*tmp[j][k][e]; 
          dp[j][val][e+1] += (1+e)*tmp[j][k][e];
        }  
      }
    }
    rep(j, 1, n) {
      rep (k, 0, l) {
        rep (e, 0, 2) {
          tmp[j][k][e] = dp[j][k][e], dp[j][k][e] = 0;
        }
      }
    }
  }
  mint ans = 0;
  rep(i, 0, l) ans += tmp[1][i][2];
  cout << ans << nl;
}

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int t = 1;
  // cin >> t;
  while (t--) { solve(); }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 472 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 472 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 340 ms 4184 KB Output is correct
23 Correct 363 ms 5212 KB Output is correct
24 Correct 338 ms 4780 KB Output is correct
25 Correct 365 ms 5204 KB Output is correct
26 Correct 315 ms 5204 KB Output is correct
27 Correct 121 ms 2396 KB Output is correct
28 Correct 160 ms 2680 KB Output is correct
29 Correct 320 ms 3964 KB Output is correct
30 Correct 356 ms 5212 KB Output is correct