oj.uz

Submission #316561

# Submission time Handle Problem Language Result Execution time Memory
316561 2020-10-26T16:31:08 Z LifeHappen__ Skyscraper (JOI16_skyscraper) C++14
100 / 100
 553 ms 362876 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ar array
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=105;
const int mod=1e9+7;
int n,a[N],b[N],L;
int f[N][N][2][2][N*10];

void add(int &x,int y){
   x=(x+y)%mod;
}

int dfs(int i,int cnt,int lef,int rig,int val){
   if(i) val+=a[i-1]*(2*cnt-lef-rig);
   if(val>L) return 0;
   int &ans=f[i][cnt][lef][rig][val];
   if(ans!=-1) return ans;
   if(i==n) return !(val>L||cnt!=1||!lef||!rig);
   ans=0;
   ///new comp
   add(ans,dfs(i+1,cnt+1,lef,rig,val)*(cnt+1-lef-rig)%mod);
   if(!lef) add(ans,dfs(i+1,cnt+1,1,rig,val));
   if(!rig) add(ans,dfs(i+1,cnt+1,lef,1,val));
   if(cnt){
      if(cnt>=2) add(ans,dfs(i+1,cnt-1,lef,rig,val)*(cnt-1)%mod);
      add(ans,dfs(i+1,cnt,lef,rig,val)*(cnt-lef)%mod);
      add(ans,dfs(i+1,cnt,lef,rig,val)*(cnt-rig)%mod);
      if(!lef) add(ans,dfs(i+1,cnt,1,rig,val));
      if(!rig) add(ans,dfs(i+1,cnt,lef,1,val));
   }
   return ans;
}

int32_t main(){
   fasty;

   cin>>n>>L;
   if(n==1) return cout<<1,0;
   forinc(i,0,n-1) cin>>b[i];
   sort(b, b+n);
   forinc(i,0,n-1) a[i]=b[i+1]-b[i];
   reset(f,-1);
   cout<<dfs(0,0,0,0,0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 203 ms 362752 KB Output is correct
3 Correct 203 ms 362876 KB Output is correct
4 Correct 202 ms 362744 KB Output is correct
5 Correct 200 ms 362744 KB Output is correct
6 Correct 204 ms 362872 KB Output is correct
7 Correct 205 ms 362744 KB Output is correct
8 Correct 204 ms 362756 KB Output is correct
9 Correct 204 ms 362872 KB Output is correct
10 Correct 205 ms 362872 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 362744 KB Output is correct
2 Correct 203 ms 362744 KB Output is correct
3 Correct 203 ms 362744 KB Output is correct
4 Correct 203 ms 362744 KB Output is correct
5 Correct 203 ms 362744 KB Output is correct
6 Correct 205 ms 362848 KB Output is correct
7 Correct 201 ms 362744 KB Output is correct
8 Correct 202 ms 362872 KB Output is correct
9 Correct 202 ms 362860 KB Output is correct
10 Correct 202 ms 362744 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 203 ms 362752 KB Output is correct
3 Correct 203 ms 362876 KB Output is correct
4 Correct 202 ms 362744 KB Output is correct
5 Correct 200 ms 362744 KB Output is correct
6 Correct 204 ms 362872 KB Output is correct
7 Correct 205 ms 362744 KB Output is correct
8 Correct 204 ms 362756 KB Output is correct
9 Correct 204 ms 362872 KB Output is correct
10 Correct 205 ms 362872 KB Output is correct
11 Correct 201 ms 362744 KB Output is correct
12 Correct 203 ms 362744 KB Output is correct
13 Correct 203 ms 362744 KB Output is correct
14 Correct 203 ms 362744 KB Output is correct
15 Correct 203 ms 362744 KB Output is correct
16 Correct 205 ms 362848 KB Output is correct
17 Correct 201 ms 362744 KB Output is correct
18 Correct 202 ms 362872 KB Output is correct
19 Correct 202 ms 362860 KB Output is correct
20 Correct 202 ms 362744 KB Output is correct
21 Correct 206 ms 362860 KB Output is correct
22 Correct 553 ms 362876 KB Output is correct
23 Correct 291 ms 362744 KB Output is correct
24 Correct 339 ms 362744 KB Output is correct
25 Correct 310 ms 362860 KB Output is correct
26 Correct 287 ms 362744 KB Output is correct
27 Correct 272 ms 362872 KB Output is correct
28 Correct 305 ms 362812 KB Output is correct
29 Correct 410 ms 362872 KB Output is correct
30 Correct 301 ms 362744 KB Output is correct