oj.uz

Submission #199373

# Submission time Handle Problem Language Result Execution time Memory
199373 2020-01-31T19:09:20 Z CaroLinda Skyscraper (JOI16_skyscraper) C++14
20 / 100
 646 ms 212088 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] ) % MOD ;
    
    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 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 46840 KB Output is correct
2 Correct 621 ms 211960 KB Output is correct
3 Correct 354 ms 151928 KB Output is correct
4 Correct 600 ms 212088 KB Output is correct
5 Correct 580 ms 211960 KB Output is correct
6 Correct 646 ms 211960 KB Output is correct
7 Correct 250 ms 120696 KB Output is correct
8 Correct 338 ms 148344 KB Output is correct
9 Correct 516 ms 204024 KB Output is correct
10 Correct 551 ms 212064 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 98 ms 46840 KB Output is correct
12 Correct 621 ms 211960 KB Output is correct
13 Correct 354 ms 151928 KB Output is correct
14 Correct 600 ms 212088 KB Output is correct
15 Correct 580 ms 211960 KB Output is correct
16 Correct 646 ms 211960 KB Output is correct
17 Correct 250 ms 120696 KB Output is correct
18 Correct 338 ms 148344 KB Output is correct
19 Correct 516 ms 204024 KB Output is correct
20 Correct 551 ms 212064 KB Output is correct
21 Incorrect 29 ms 21368 KB Output isn't correct
22 Halted 0 ms 0 KB -