Submission #598024

#	Time	Username	Problem	Language	Result	Execution time	Memory
598024		isaachew	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	172 ms	99704 KiB

skyscraper

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80