oj.uz

Submission #257880

# Submission time Handle Problem Language Result Execution time Memory
257880 2020-08-05T00:19:26 Z NaimSS Skyscraper (JOI16_skyscraper) C++14
100 / 100
 305 ms 252152 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

const int N = 103;
const int M = 1e9 + 7;

ll dp[N][1010][N][3];
int a[N];

int n,L;
ll solve(int i,int l,int k,int t){
    // tem k componentes, tem t pontas
    if(k < 0)return 0;
    
    if(i)l+= (a[i] - a[i-1])*(2*k + t);

    if(l > L)return 0;

    if(i == n - 1){
        return !k;
    }

    ll &x = dp[i][l][k][t];
    if(x!=-1)return x;
    x=0;

    // coisa das pontas
    
    if(t == 0){
      // pode criar qq um dos dois lados
      x += 2ll * solve(i+1,l,k,1);
      x += 2ll * k * solve(i+1,l,k-1,1); // cria e ja da merge
    }
    if(t == 1){
      // no lado q ja tem
      x += solve(i+1,l,k,1);
      x += 1ll * k * solve(i+1,l,k-1,1);

      // cria um novo
      x += 1ll * solve(i+1,l,k,2);
      x += 1ll * k * solve(i+1,l,k-1,2);
    }
    if(t == 2){
      // so junta ou dá merge com qq um dos lados
      x += 2ll *solve(i+1,l,k,t) + 2ll * k * solve(i+1,l,k-1,t);
    }

    // now the middle stuff    

    // isolado
    x += solve(i+1,l,k+1,t);

    // merge with one ( to the left/right of it)
    x += 2ll*k*solve(i+1,l,k,t);

    // merge two boys
    x += 1ll * k * (k-1) * solve(i+1,l,k-1,t);

    x%=M;
    return x;
}


int32_t main(){
  fastio;
  cin >> n >> L;

  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a,a+n);

  ms(dp,-1);

  cout << solve(0,0,0,0) << endl; 

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
  
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 252024 KB Output is correct
2 Correct 127 ms 251896 KB Output is correct
3 Correct 131 ms 251968 KB Output is correct
4 Correct 128 ms 252024 KB Output is correct
5 Correct 130 ms 252024 KB Output is correct
6 Correct 128 ms 251896 KB Output is correct
7 Correct 128 ms 251900 KB Output is correct
8 Correct 131 ms 251896 KB Output is correct
9 Correct 129 ms 251976 KB Output is correct
10 Correct 127 ms 251896 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 251896 KB Output is correct
2 Correct 139 ms 251920 KB Output is correct
3 Correct 144 ms 251900 KB Output is correct
4 Correct 132 ms 251772 KB Output is correct
5 Correct 142 ms 251896 KB Output is correct
6 Correct 130 ms 251896 KB Output is correct
7 Correct 143 ms 251912 KB Output is correct
8 Correct 143 ms 251896 KB Output is correct
9 Correct 141 ms 251896 KB Output is correct
10 Correct 129 ms 251896 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 252024 KB Output is correct
2 Correct 127 ms 251896 KB Output is correct
3 Correct 131 ms 251968 KB Output is correct
4 Correct 128 ms 252024 KB Output is correct
5 Correct 130 ms 252024 KB Output is correct
6 Correct 128 ms 251896 KB Output is correct
7 Correct 128 ms 251900 KB Output is correct
8 Correct 131 ms 251896 KB Output is correct
9 Correct 129 ms 251976 KB Output is correct
10 Correct 127 ms 251896 KB Output is correct
11 Correct 127 ms 251896 KB Output is correct
12 Correct 139 ms 251920 KB Output is correct
13 Correct 144 ms 251900 KB Output is correct
14 Correct 132 ms 251772 KB Output is correct
15 Correct 142 ms 251896 KB Output is correct
16 Correct 130 ms 251896 KB Output is correct
17 Correct 143 ms 251912 KB Output is correct
18 Correct 143 ms 251896 KB Output is correct
19 Correct 141 ms 251896 KB Output is correct
20 Correct 129 ms 251896 KB Output is correct
21 Correct 139 ms 251896 KB Output is correct
22 Correct 305 ms 251896 KB Output is correct
23 Correct 291 ms 251956 KB Output is correct
24 Correct 252 ms 251896 KB Output is correct
25 Correct 283 ms 252024 KB Output is correct
26 Correct 250 ms 251992 KB Output is correct
27 Correct 162 ms 251896 KB Output is correct
28 Correct 175 ms 252152 KB Output is correct
29 Correct 263 ms 252024 KB Output is correct
30 Correct 282 ms 251896 KB Output is correct