oj.uz

Submission #1079357

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

const long long mod=1e9+7;

int n,s,a[MAXN],ans;

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

long long even(int pos,int bal,int sum,int l,int r){
    if(bal<0 or bal>n or sum>s)return 0;

    long long 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].find(sum)!=dp[pos][bal][l][r].end())return dp[pos][bal][l][r][sum];
    long long curr=0;

    curr+=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);
    }

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

    curr+=even(pos+1,bal+1,sum-2*a[pos],l,r)*mult;
    curr+=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;
    }

    calc_even();

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

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 21 ms 10332 KB Output is correct
3 Correct 8 ms 7000 KB Output is correct
4 Correct 21 ms 10588 KB Output is correct
5 Correct 24 ms 11100 KB Output is correct
6 Correct 14 ms 9308 KB Output is correct
7 Correct 10 ms 7772 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 8 ms 7260 KB Output is correct
10 Correct 26 ms 9416 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5980 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 2 ms 6080 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 5 ms 6236 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Correct 4 ms 6236 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 4 ms 6236 KB Output is correct
10 Correct 3 ms 6236 KB Output is correct
11 Correct 4 ms 6492 KB Output is correct
12 Correct 21 ms 10332 KB Output is correct
13 Correct 8 ms 7000 KB Output is correct
14 Correct 21 ms 10588 KB Output is correct
15 Correct 24 ms 11100 KB Output is correct
16 Correct 14 ms 9308 KB Output is correct
17 Correct 10 ms 7772 KB Output is correct
18 Correct 7 ms 6996 KB Output is correct
19 Correct 8 ms 7260 KB Output is correct
20 Correct 26 ms 9416 KB Output is correct
21 Correct 440 ms 67644 KB Output is correct
22 Execution timed out 2076 ms 268172 KB Time limit exceeded
23 Halted 0 ms 0 KB -