oj.uz

Submission #316560

# Submission time Handle Problem Language Result Execution time Memory
316560 2020-10-26T16:29:02 Z LifeHappen__ Skyscraper (JOI16_skyscraper) C++14
15 / 100
 205 ms 362964 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;
   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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 362964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 362964 KB Output isn't correct
2 Halted 0 ms 0 KB -