oj.uz

Submission #316413

# Submission time Handle Problem Language Result Execution time Memory
316413 2020-10-26T10:02:27 Z vipghn2003 Skyscraper (JOI16_skyscraper) C++14
5 / 100
 108 ms 181752 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=105;
const int mod=1e9+7;

int n,L,a[N],b[N];
int dp[N][N][2][2][N*10];

int calc(int i,int cnt,bool haveL,bool haveR,int val)
{
   if(i) val+=a[i]*(2*cnt-haveL-haveR);
   if(val>L) return 0;
   int &res=dp[i][cnt][haveL][haveR][val];
   if(res!=-1) return res;
   if(i==n)
   {
      if(val>L||cnt!=1||!haveL||!haveR) return 0;
      return 1;
   }
   res=0;
   ///new comp
   res+=calc(i+1,cnt+1,haveL,haveR,val)*(cnt+1-haveL-haveR);
   ///new L
   if(!haveL) res+=calc(i+1,cnt+1,1,haveR,val);
   ///new R
   if(!haveR) res+=calc(i+1,cnt+1,haveL,1,val);
   if(cnt)
   {
       ///merge
       if(cnt>=2) res+=calc(i+1,cnt-1,haveL,haveR,val)*(cnt-1);
       ///push front
       res+=calc(i+1,cnt,haveL,haveR,val)*(cnt-haveL);
       ///push back
       res+=calc(i+1,cnt,haveL,haveR,val)*(cnt-haveR);
       ///made L
       if(!haveL) res+=calc(i+1,cnt,1,haveR,val);
       ///made R
       if(!haveR) res+=calc(i+1,cnt,haveL,1,val);
   }
   //cout<<i<<' '<<cnt<<' '<<haveL<<' '<<haveR<<' '<<val<<'\n' ;
   return res;
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   memset(dp,-1,sizeof dp);
   cin>>n>>L;
   if(n==1) return cout<<1,0;
   for(int i=1;i<=n;i++) cin>>b[i];
   sort(b+1,b+n+1);
   for(int i=0;i<n;i++) a[i]=b[i+1]-b[i];
   cout<<calc(0,0,0,0,0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 181624 KB Output is correct
2 Correct 102 ms 181624 KB Output is correct
3 Correct 105 ms 181628 KB Output is correct
4 Correct 101 ms 181604 KB Output is correct
5 Correct 106 ms 181496 KB Output is correct
6 Correct 103 ms 181496 KB Output is correct
7 Correct 105 ms 181752 KB Output is correct
8 Correct 103 ms 181496 KB Output is correct
9 Correct 104 ms 181680 KB Output is correct
10 Correct 105 ms 181496 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 181496 KB Output is correct
2 Correct 104 ms 181496 KB Output is correct
3 Correct 108 ms 181496 KB Output is correct
4 Correct 106 ms 181500 KB Output is correct
5 Correct 106 ms 181496 KB Output is correct
6 Correct 104 ms 181624 KB Output is correct
7 Correct 103 ms 181624 KB Output is correct
8 Correct 104 ms 181500 KB Output is correct
9 Incorrect 105 ms 181624 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 181624 KB Output is correct
2 Correct 102 ms 181624 KB Output is correct
3 Correct 105 ms 181628 KB Output is correct
4 Correct 101 ms 181604 KB Output is correct
5 Correct 106 ms 181496 KB Output is correct
6 Correct 103 ms 181496 KB Output is correct
7 Correct 105 ms 181752 KB Output is correct
8 Correct 103 ms 181496 KB Output is correct
9 Correct 104 ms 181680 KB Output is correct
10 Correct 105 ms 181496 KB Output is correct
11 Correct 102 ms 181496 KB Output is correct
12 Correct 104 ms 181496 KB Output is correct
13 Correct 108 ms 181496 KB Output is correct
14 Correct 106 ms 181500 KB Output is correct
15 Correct 106 ms 181496 KB Output is correct
16 Correct 104 ms 181624 KB Output is correct
17 Correct 103 ms 181624 KB Output is correct
18 Correct 104 ms 181500 KB Output is correct
19 Incorrect 105 ms 181624 KB Output isn't correct
20 Halted 0 ms 0 KB -