oj.uz

Submission #199372

# Submission time Handle Problem Language Result Execution time Memory
199372 2020-01-31T19:08:03 Z CaroLinda Skyscraper (JOI16_skyscraper) C++14
5 / 100
 1354 ms 212020 KB 
#include <bits/stdc++.h>

const int MOD = 1e9+7 ;
const int MAXL = 110 ;
const int MAXN = 15 ;

using namespace std ;

int n , l ;
int f[MAXN] ;
long long dp[ (1<<14)+100 ][ MAXL ][ MAXN ] ;

bool isOn(int mask, int i) { return ((1<<i)&mask) != 0 ; } 


int main()
{
    
    scanf("%d%d", &n , &l ) ;
    for(int i = 1 ; i <= n ; i++ ) scanf("%d", &f[i]) ;
    
    if( n <= 8 )
    {
        
        sort( f+1, f+1+n ) ;
        
        int ans = 0 , soma = 0 ;
        
        for(int i = 1 ; i < n ; i++ )
                soma += abs( f[i] - f[i+1] ) ;
        if( soma <= l ) ans ++ ;
        while( next_permutation( f+1, f+1+n ) )
        {
            soma = 0;
            
            for(int i = 1 ; i < n ; i++ )
                soma += abs( f[i] - f[i+1] ) ;
            if( soma <= l ) ans ++ ;
        }
        
        printf("%d\n" , ans ) ;
        return 0 ;
        
    } 
    
    long long ans = 0LL ;
    
    for(int i = l ; i >= 0 ; i-- )
        for(int j = 0 ; j < n ; j++ ) dp[ (1<<n)-1 ][i][j] = 1 ;
    
    for(int mask = (1<<n) - 2 ; mask > 0 ; mask--  )
    {
        
        vector<int> off , on ;
        
        for(int i = 0 ; i < n ; i++ )
        {
            if( isOn(mask, i) ) on.push_back(i) ;
            else off.push_back(i) ;
        }
        
        for(int i = 0 ; i <= l ; i++ )
            for(int j : on )
                for(int k : off)
                {
                    if( i < abs( f[j+1] - f[k+1] ) ) continue ;
                    dp[mask][i][j] = (dp[mask][i][j] + dp[ mask|(1<<k) ][ i - abs( f[j+1] - f[k+1] ) ][ k ] ) % MOD ;
                }
            
            
    }
    
    for(int i = 0 ; i < n ; i++ ) ans = ( ans + dp[ (1<<i) ][l][i] ) ;
    
    printf("%lld\n" , ans ) ;
    
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n , &l ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1 ; i <= n ; i++ ) scanf("%d", &f[i]) ;
                                    ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 46840 KB Output is correct
2 Correct 1354 ms 212020 KB Output is correct
3 Correct 339 ms 151928 KB Output is correct
4 Correct 885 ms 211960 KB Output is correct
5 Correct 637 ms 211960 KB Output is correct
6 Correct 602 ms 211960 KB Output is correct
7 Correct 241 ms 120696 KB Output is correct
8 Correct 345 ms 148216 KB Output is correct
9 Incorrect 529 ms 203896 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 94 ms 46840 KB Output is correct
12 Correct 1354 ms 212020 KB Output is correct
13 Correct 339 ms 151928 KB Output is correct
14 Correct 885 ms 211960 KB Output is correct
15 Correct 637 ms 211960 KB Output is correct
16 Correct 602 ms 211960 KB Output is correct
17 Correct 241 ms 120696 KB Output is correct
18 Correct 345 ms 148216 KB Output is correct
19 Incorrect 529 ms 203896 KB Output isn't correct
20 Halted 0 ms 0 KB -