Submission #199911

#	Time	Username	Problem	Language	Result	Execution time	Memory
199911		CaroLinda	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	483 ms	6780 KiB

skyscraper

#include <bits/stdc++.h>

const int MOD = 1e9+7 ;
const int MAXN = 105 ;
const int MAXL = 1005 ;

using namespace std ;

int N , L ; 
int F[MAXN] , idx[MAXN] ;
long long dp[2][2][MAXN][2][MAXL] ;

inline void f(long long &x, long long y) { x = (x+y) % MOD ; }

int main()
{
	scanf("%d%d", &N , &L ) ;
	for(int i = 1 ; i <= N ; i++ ) scanf("%d", &F[i] ) ;
	sort(F+1, F+1+N ) ;

	if( N == 1 )
	{
		printf("1\n") ;
		return 0 ;
	}

	for(int i = 1 ; i<= N+1 ; i++ ) idx[i] = i%2 ;

	for(int i = N ; i > 0 ; i-- )
		for(int lef = 0 ; lef < 2 ; lef++ )
			for(int c = 0 ; c <= N ; c++ )
				for(int rig = 0 ; rig < 2 ; rig ++ )
					for(int cost = 0 ; cost <= L ; cost ++ )
					{


						long long &x = dp[ idx[i] ][lef][c][rig][cost] ;
						x = 0 ;
						int new_cost = cost + ( F[i] - F[i-1] ) * ( 2*c + lef + rig ) ;

						if( new_cost > L ) continue ;

						int id = idx[i+1] ;

						if( i == N )
						{
							x = ( c == 0 ? 1 : 0 ) ;
							continue ;
						}

						if( c > 0 )
						{
							f( x , dp[id][1][c-1][rig][new_cost] * c ) ; 
							f( x , dp[id][lef][c-1][1][new_cost] * c ) ;
							f( x , dp[id][lef][c-1][rig][new_cost] * c * (c-1) ) ;
						}

						f( x , dp[id][1][c][rig][ new_cost ] ) ; //soh coloquei na esquerda 

						f( x , dp[id][lef][c][1][ new_cost ] ) ;

						f( x , dp[id][lef][c+1][rig][ new_cost ] ) ;
						f( x , dp[id][lef][c][rig][ new_cost ] * 2 * c ) ;


					}

		printf("%lld\n" , dp[1][0][0][0][0]) ;

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i = N ; i > 0 ; i-- )
  ^~~
skyscraper.cpp:68:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   printf("%lld\n" , dp[1][0][0][0][0]) ;
   ^~~~~~
skyscraper.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N , &L ) ;
  ~~~~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:18:38: 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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80