oj.uz

Submission #1079434

# Submission time Handle Problem Language Result Execution time Memory
1079434 2024-08-28T14:37:20 Z alexander707070 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 241352 KB 
#include<bits/stdc++.h>
#define MAXN 107
using namespace std;

const int mod=1e9+7;

int n,s,a[MAXN],ans,pref[2*MAXN];

unordered_map<int,int> dp[MAXN][MAXN][3][3];

int even(int pos,int bal,int sum,int l,int r){

    if(sum>s or bal>n)return 0;
    if(sum+2*(pref[pos+(bal-n/2)-2]-pref[pos-1])>s)return 0;

    int free=2*(bal-n/2)+(-(l==1)-(r==1)) - (-(l==2)-(r==2));
    if(free<0)return 0;

    if(pos==n+1 and bal==n/2 and l+r==3 and free==0)return 1;
    else if(pos==n+1 and (bal==n/2-1 or bal==n/2+1) and l==r and l!=0 and free==0)return 1;
    else if(pos==n+1)return 0;

    if(free==0 and pos!=1)return 0;

    if(dp[pos][bal][l][r].count(sum))return dp[pos][bal][l][r][sum];
    long long curr=0;

    curr+=1LL*even(pos+1,bal,sum,l,r)*free;

    if(l==0){
        curr+=even(pos+1,bal+1,sum-a[pos],1,r);
        curr+=even(pos+1,bal-1,sum+a[pos],2,r);
    }

    if(r==0){
        curr+=even(pos+1,bal+1,sum-a[pos],l,1);
        curr+=even(pos+1,bal-1,sum+a[pos],l,2);
    }

    int mult=bal-n/2+1-(l==1)-(r==1);
    int mult2=bal-n/2-1+(l==2)+(r==2);

    curr+=1LL*even(pos+1,bal+1,sum-2*a[pos],l,r)*mult;
    curr+=1LL*even(pos+1,bal-1,sum+2*a[pos],l,r)*mult2;

    curr%=mod;
    dp[pos][bal][l][r][sum]=curr;

    return curr;
}

void calc_even(){
    ans+=even(1,n/2,0,0,0);
}

int main(){

    cin>>n>>s;

    int mins=1000;

    if(n==1){
        cout<<1<<"\n";
        return 0;
    }

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

    mins=a[1];

    for(int i=1;i<=n;i++){
        a[i]-=mins;
        pref[i]=pref[i-1]+a[i];
    }

    for(int i=n+1;i<=2*n;i++){
        pref[i]=pref[i-1];
    }

    calc_even();

    cout<<ans%mod<<"\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6080 KB Output is correct
2 Correct 2 ms 5976 KB Output is correct
3 Correct 2 ms 5976 KB Output is correct
4 Correct 2 ms 6084 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 6192 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6488 KB Output is correct
2 Correct 7 ms 6956 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 5 ms 6972 KB Output is correct
5 Correct 6 ms 7004 KB Output is correct
6 Correct 7 ms 7256 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 8 ms 6856 KB Output is correct
10 Correct 5 ms 6744 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6080 KB Output is correct
2 Correct 2 ms 5976 KB Output is correct
3 Correct 2 ms 5976 KB Output is correct
4 Correct 2 ms 6084 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 6192 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 5 ms 6488 KB Output is correct
12 Correct 7 ms 6956 KB Output is correct
13 Correct 5 ms 6748 KB Output is correct
14 Correct 5 ms 6972 KB Output is correct
15 Correct 6 ms 7004 KB Output is correct
16 Correct 7 ms 7256 KB Output is correct
17 Correct 3 ms 6492 KB Output is correct
18 Correct 4 ms 6748 KB Output is correct
19 Correct 8 ms 6856 KB Output is correct
20 Correct 5 ms 6744 KB Output is correct
21 Correct 16 ms 9820 KB Output is correct
22 Execution timed out 2101 ms 241352 KB Time limit exceeded
23 Halted 0 ms 0 KB -