oj.uz

Submission #343188

# Submission time Handle Problem Language Result Execution time Memory
343188 2021-01-03T13:28:48 Z Nursik Skyscraper (JOI16_skyscraper) C++14
20 / 100
 465 ms 230764 KB 
#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
} 

int n, l, cur;
int a[30];
ll dp[2][15][20000][101];
vector<int> g[20];
vector<int> g2[20000];
main()
{
	data();
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);	
	cin >> n >> l;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}       
	if (n <= 8)
	{
		vector<int> v;
		for (int i = 1; i <= n; i++)
		{
			v.pb(a[i]);
		}
		sort(all(v));
		int ans = 0;
		do
		{
			ll sum = 0;
			for (int i = 1; i < v.size(); i++)
			{
				sum += abs(v[i] - v[i - 1]);
			}
			if (sum <= l)
			{
				ans++;
			}
		} while(next_permutation(all(v)));
		cout << ans << '\n';
		return 0;
	}
	//optim
	for (int j = 0; j < (1 << n); j++)
	{
		g[__builtin_popcount(j)].pb(j);
		for (int i = 0; i < n; i ++)
		{
			if ((j & (1 << i)))
			{
			}
			else
			{
				g2[j].pb(i);
			}
		}	
	}
	//endoptim
	for (int i = 0; i < g[1].size(); i++)
	{
		int k = g[1][i], bit = 0;
		for (int j = 0; j < n; j++)
		{
			if (k >> j & 1)
				bit = j;	
		}
		dp[0][bit][k][0] = 1;
	}
	//cout << g2[0][0] << '\n';
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < g[i - 1].size(); j++)
		{
			int mask = g[i - 1][j];
			for (int k = 0; k < n; k++)
			{
				for (int sum = 0; sum <= l; sum++)
				{
					if (dp[cur][k][mask][sum] > 0)
					{              			
						for (int ind = 0; ind < g2[mask].size(); ind++)
						{
							int nwbit = g2[mask][ind];
							if (sum + abs(a[k + 1] - a[nwbit + 1]) <= l)
							{
								dp[cur ^ 1][nwbit][(mask ^ (1 << nwbit))][sum + abs(a[k + 1] - a[nwbit + 1])] += dp[cur][k][mask][sum];
						    	dp[cur ^ 1][nwbit][(mask ^ (1 << nwbit))][sum + abs(a[k + 1] - a[nwbit + 1])] %= mod;
							}
						}
						dp[cur][k][mask][sum] = 0;     
					}
				}
			}
		}
		cur ^= 1;
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= l; j++)
		{
			ans += dp[cur][i][(1 << n) - 1][j];
			ans %= mod;
		}
	}
	cout << ans;

}
/*
6 4 2
2 9 2 3 8 5




*/

Compilation message

skyscraper.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main()
      |      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for (int i = 1; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
skyscraper.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0; i < g[1].size(); i++)
      |                  ~~^~~~~~~~~~~~~
skyscraper.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int j = 0; j < g[i - 1].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:111:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |       for (int ind = 0; ind < g2[mask].size(); ind++)
      |                         ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 51564 KB Output is correct
2 Correct 217 ms 168556 KB Output is correct
3 Correct 359 ms 229356 KB Output is correct
4 Correct 203 ms 153452 KB Output is correct
5 Correct 168 ms 101516 KB Output is correct
6 Correct 361 ms 230764 KB Output is correct
7 Correct 164 ms 126144 KB Output is correct
8 Correct 352 ms 229356 KB Output is correct
9 Correct 465 ms 230764 KB Output is correct
10 Correct 193 ms 141164 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 76 ms 51564 KB Output is correct
12 Correct 217 ms 168556 KB Output is correct
13 Correct 359 ms 229356 KB Output is correct
14 Correct 203 ms 153452 KB Output is correct
15 Correct 168 ms 101516 KB Output is correct
16 Correct 361 ms 230764 KB Output is correct
17 Correct 164 ms 126144 KB Output is correct
18 Correct 352 ms 229356 KB Output is correct
19 Correct 465 ms 230764 KB Output is correct
20 Correct 193 ms 141164 KB Output is correct
21 Runtime error 25 ms 1516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -