oj.uz

Submission #297036

# Submission time Handle Problem Language Result Execution time Memory
297036 2020-09-11T08:09:01 Z arnold518 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 975 ms 400560 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 14;
const ll MOD = 1e9+7;

int N, L, A[MAXN+10];
ll dp[(1<<MAXN)][MAXN][110];

ll solve(int mask, int bef, int sum)
{
	if(sum>L) return 0;
	if(mask==((1<<N)-1)) return 1;
	ll &ret=dp[mask][bef][sum];
	if(ret!=-1) return ret;

	ret=0;
	for(int i=0; i<N; i++)
	{
		if(mask&(1<<i)) continue;
		ret+=solve(mask|(1<<i), i, sum+abs(A[i]-A[bef]));
		ret%=MOD;
	}
	return ret;
}

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

	memset(dp, -1, sizeof(dp));

	ll ans=0;
	for(int i=0; i<N; i++) ans=(ans+solve((1<<i), i, 0))%MOD;
	printf("%lld\n", ans);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d%d", &N, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:34:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  for(int i=0; i<N; i++) scanf("%d", &A[i]);
      |                         ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 197752 KB Output is correct
2 Correct 110 ms 197824 KB Output is correct
3 Correct 109 ms 197752 KB Output is correct
4 Correct 113 ms 197752 KB Output is correct
5 Correct 112 ms 197880 KB Output is correct
6 Correct 110 ms 197752 KB Output is correct
7 Correct 108 ms 197752 KB Output is correct
8 Correct 112 ms 197848 KB Output is correct
9 Correct 113 ms 197880 KB Output is correct
10 Correct 109 ms 197752 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 197880 KB Output is correct
2 Correct 167 ms 197880 KB Output is correct
3 Correct 683 ms 197752 KB Output is correct
4 Correct 152 ms 197752 KB Output is correct
5 Correct 133 ms 197752 KB Output is correct
6 Correct 658 ms 197752 KB Output is correct
7 Correct 141 ms 197880 KB Output is correct
8 Correct 643 ms 197752 KB Output is correct
9 Correct 975 ms 197880 KB Output is correct
10 Correct 163 ms 197752 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 197752 KB Output is correct
2 Correct 110 ms 197824 KB Output is correct
3 Correct 109 ms 197752 KB Output is correct
4 Correct 113 ms 197752 KB Output is correct
5 Correct 112 ms 197880 KB Output is correct
6 Correct 110 ms 197752 KB Output is correct
7 Correct 108 ms 197752 KB Output is correct
8 Correct 112 ms 197848 KB Output is correct
9 Correct 113 ms 197880 KB Output is correct
10 Correct 109 ms 197752 KB Output is correct
11 Correct 189 ms 197880 KB Output is correct
12 Correct 167 ms 197880 KB Output is correct
13 Correct 683 ms 197752 KB Output is correct
14 Correct 152 ms 197752 KB Output is correct
15 Correct 133 ms 197752 KB Output is correct
16 Correct 658 ms 197752 KB Output is correct
17 Correct 141 ms 197880 KB Output is correct
18 Correct 643 ms 197752 KB Output is correct
19 Correct 975 ms 197880 KB Output is correct
20 Correct 163 ms 197752 KB Output is correct
21 Correct 110 ms 197880 KB Output is correct
22 Runtime error 354 ms 400560 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -