oj.uz

Submission #1031517

# Submission time Handle Problem Language Result Execution time Memory
1031517 2024-07-22T23:19:35 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
20 / 100
 138 ms 179028 KB 
#include<bits/stdc++.h>
using namespace std;
//int dp0[101][51],dp1[105][51],dp2[101][51];
long long cnt1[1<<14][14][101],cnt2[1<<8][8][1010];
int vl[14],mod=1e9+7;
int main(){
    int n,l;
    cin>>n>>l;
    if(n>8){
        for(int i=0;i<n;i++)
            cin>>vl[i],cnt1[1<<i][i][0]=1;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i&1<<j) {
                for(int k=0;k<=l;k++)
                    cnt1[i][j][k]%=mod;
                for(int k=0;k<n;k++)if(~i&1<<k){
                    int cst=abs(vl[j]-vl[k]);
                    for(int v=0;v<=l-cst;v++)
                        cnt1[i^1<<k][k][v+cst]+=cnt1[i][j][v];
                }
            }
        long long ans=0;
        for(int i=0;i<=l;i++)
            for(int x=0;x<n;x++)
                ans+=cnt1[(1<<n)-1][x][i];
        cout<<ans%mod;
    } else {
        for(int i=0;i<n;i++)
            cin>>vl[i],cnt2[1<<i][i][0]=1;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i&1<<j) {
                for(int k=0;k<=l;k++)
                    cnt2[i][j][k]%=mod;
                for(int k=0;k<n;k++)if(~i&1<<k){
                    int cst=abs(vl[j]-vl[k]);
                    for(int v=0;v<=l-cst;v++)
                        cnt2[i^1<<k][k][v+cst]+=cnt2[i][j][v];
                }
            }
        long long ans=0;
        for(int i=0;i<=l;i++)
            for(int x=0;x<n;x++)
                ans+=cnt2[(1<<n)-1][x][i];

        cout<<ans%mod;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 7 ms 10332 KB Output is correct
6 Correct 7 ms 9820 KB Output is correct
7 Correct 3 ms 5720 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 6 ms 10076 KB Output is correct
10 Correct 3 ms 5460 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 43604 KB Output is correct
2 Correct 133 ms 179024 KB Output is correct
3 Correct 96 ms 177340 KB Output is correct
4 Correct 119 ms 179028 KB Output is correct
5 Correct 138 ms 179028 KB Output is correct
6 Correct 132 ms 178972 KB Output is correct
7 Correct 88 ms 176688 KB Output is correct
8 Correct 96 ms 177232 KB Output is correct
9 Correct 117 ms 178004 KB Output is correct
10 Correct 119 ms 178380 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 7 ms 10332 KB Output is correct
6 Correct 7 ms 9820 KB Output is correct
7 Correct 3 ms 5720 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 6 ms 10076 KB Output is correct
10 Correct 3 ms 5460 KB Output is correct
11 Correct 26 ms 43604 KB Output is correct
12 Correct 133 ms 179024 KB Output is correct
13 Correct 96 ms 177340 KB Output is correct
14 Correct 119 ms 179028 KB Output is correct
15 Correct 138 ms 179028 KB Output is correct
16 Correct 132 ms 178972 KB Output is correct
17 Correct 88 ms 176688 KB Output is correct
18 Correct 96 ms 177232 KB Output is correct
19 Correct 117 ms 178004 KB Output is correct
20 Correct 119 ms 178380 KB Output is correct
21 Runtime error 3 ms 604 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -