oj.uz

Submission #598024

# Submission time Handle Problem Language Result Execution time Memory
598024 2022-07-17T11:16:21 Z isaachew Skyscraper (JOI16_skyscraper) C++17
20 / 100
 172 ms 99704 KB 
#include <bits/stdc++.h>
/*
 Ascending = no cost
 Descending = cost of double AD (difference from normal differences)
 Add regular difference (end - start)?
 
 For every start and end skyscraper, DP over cost (cost <= 1000)?
 Inversions are what matters
 
 Iterate over buildings in sorted order
 The next building will cause an inversion unless placed at end
 
 Either cause an inversion or change the difference by placing at end
 The difference is stored with the inversions
 
 As the new element is inserted, an inversion might be replaced
 
 The old last element is not stored
 
 
 O(N^2L) ~ 10^7
 
 Count number of permutations where a certain number is "exposed" once/twice
 */
int n,l;
std::vector<int> builds;

int main(){
    std::cin>>n>>l;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        builds.push_back(x);
    }
    std::sort(builds.begin(),builds.end());
    if(n<=14){
        std::vector<std::vector<std::vector<int>>> vec(1<<n,std::vector<std::vector<int>>(n,std::vector<int>(l+1)));
        for(int i=0;i<n;i++){
            vec[1<<i][i][0]=1;
        }
        for(int e=0;e<1<<n;e++){
            if(e==(e&-e))continue;
            for(int x=0;x<n;x++){
                if(((e>>x)&1)==0)continue;
                int pid=e^(1<<x);
                std::vector<int> cur(l+1);
                for(int y=0;y<n;y++){
                    if(((e>>y)&1)==0||x==y)continue;
                    int offs=builds[x]-builds[y];
                    if(offs<0)offs=-offs;
                    for(int c=offs;c<=l;c++){
                        cur[c]+=vec[pid][y][c-offs];
                        cur[c]%=1000000007;
                    }
                }
                vec[e][x]=cur;
            }
        }
        int result=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<=l;j++){
                result+=vec[(1<<n)-1][i][j];
                result%=1000000007;
            }
        }
        std::cout<<result<<'\n';
        return 0;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 7 ms 7988 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 7 ms 7636 KB Output is correct
10 Correct 2 ms 1284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14676 KB Output is correct
2 Correct 172 ms 96100 KB Output is correct
3 Correct 101 ms 49420 KB Output is correct
4 Correct 169 ms 96132 KB Output is correct
5 Correct 157 ms 99704 KB Output is correct
6 Correct 169 ms 92492 KB Output is correct
7 Correct 67 ms 35028 KB Output is correct
8 Correct 100 ms 49424 KB Output is correct
9 Correct 152 ms 74444 KB Output is correct
10 Correct 147 ms 85288 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 7 ms 7988 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 7 ms 7636 KB Output is correct
10 Correct 2 ms 1284 KB Output is correct
11 Correct 31 ms 14676 KB Output is correct
12 Correct 172 ms 96100 KB Output is correct
13 Correct 101 ms 49420 KB Output is correct
14 Correct 169 ms 96132 KB Output is correct
15 Correct 157 ms 99704 KB Output is correct
16 Correct 169 ms 92492 KB Output is correct
17 Correct 67 ms 35028 KB Output is correct
18 Correct 100 ms 49424 KB Output is correct
19 Correct 152 ms 74444 KB Output is correct
20 Correct 147 ms 85288 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -