oj.uz

Submission #98481

# Submission time Handle Problem Language Result Execution time Memory
98481 2019-02-23T18:37:34 Z luciocf Zoltan (COCI16_zoltan) C++14
42 / 140
 713 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 22;
const int mod = 1e9+7;

typedef long long ll;

int num[maxn], dp[maxn];

ll qtd[maxn];

int main(void)
{
	int n;
	ll q = 0LL;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];

	int ans = 0;

	for (int mask = 0; mask < (1<<n); mask++)
	{
		int aux = 0;

		deque<int> dq;

		if (!(mask&1)) continue;

		for (int i = 0; i < n; i++)
		{
			if (mask&(1<<i)) dq.push_front(num[i]);
			else dq.push_back(num[i]);
		}

		vector<int> v;

		while (dq.size() > 0)
		{
			v.push_back(dq.front());
			dq.pop_front();
		}	

		memset(qtd, 0, sizeof qtd);

		for (int i = 0; i < v.size(); i++)
		{
			dp[i] = 1;
			for (int j = 0; j < i; j++)
				if (v[j] < v[i]) 
					dp[i] = max(dp[i], dp[j]+1);
		}

		for (int i = 0; i < v.size(); i++)
		{
			aux = max(aux, dp[i]);
			if (dp[i] == 1) qtd[i] = 1LL;
		} 

		if (aux < ans) continue;
		
		if (aux > ans) q = 0LL;
		ans = aux;

		for (int i = 0; i < v.size(); i++)
			for (int j = 0; j < i; j++)
				if (v[j] < v[i] && dp[j]+1 == dp[i])
					qtd[i] = (qtd[i]+qtd[j])%mod;

		for (int i = 0; i < v.size(); i++)
			if (dp[i] == ans) q = (q+qtd[i])%mod;
	}

	cout << ans << " " << q << "\n";
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++)
                   ~~^~~~~~~~~~
zoltan.cpp:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++)
                   ~~^~~~~~~~~~
zoltan.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++)
                   ~~^~~~~~~~~~
zoltan.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++)
                   ~~^~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 360 KB Output is correct
2 Correct 646 ms 376 KB Output is correct
3 Correct 656 ms 356 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 585 ms 376 KB Output is correct
6 Correct 713 ms 380 KB Output is correct
7 Runtime error 3 ms 484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 4 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)