oj.uz

Submission #98504

# Submission time Handle Problem Language Result Execution time Memory
98504 2019-02-23T19:42:58 Z thiago4532 Zoltan (COCI16_zoltan) C++17
21 / 140
 1000 ms 10060 KB 
#include <bits/stdc++.h>
// #define int int64_t
#define int uint_fast32_t
 
using namespace std;
const int maxn = 1010;
int v[maxn], dp[maxn], dp2[maxn], i;
deque<int> dq;
int ct=0, n;
 
void backtracking(int i, deque<int> const& d){
	if(i == n){
		if(d == dq) ct++;
		return;
	}
 
	deque<int> d1 = d, d2 = d;
	d1.push_back(v[i]);
	d2.push_front(v[i]);
	backtracking(i+1, d1);
	backtracking(i+1, d2);
}
 
int lis(){
	
	vector<int> pilha;
	
	for(int i=0; i<n; i++){
		vector<int>::iterator it = lower_bound(pilha.begin(), pilha.end(), v[i]);
		if(it==pilha.end()) pilha.push_back(v[i]);
		else *it = v[i];
	}
	
	return pilha.size();
}
 
int32_t main(){
	cin >> n;
 
	int aux;
	cin >> aux;
	dq.push_back(aux);
 
	for(int i=2;i<=n;i++){
		int x;
		cin >> x;
		if(x <= dq[0]) dq.push_front(x);
		else dq.push_back(x);
	}
	for(int i=0;i<n;i++)
		v[i] = dq[i];

	backtracking(1, deque<int>({v[0]}));
	
	//for(int i=0;i<n;i++)
	//	cin >> v[i];


	dp[0] = 1;
	dp2[0] = 1;

	for(int i = 1; i < n; i++){
		dp[i] = dp2[i] = 1;

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

		if(dp[i] == 1) continue;

		dp2[i] = 0;
		for(int j = 0; j < i; j++)
			if(v[j] < v[i] && dp[j] + 1 == dp[i]) dp2[i] += dp2[j];
	}

	int a = 0, b = 0;

	for(int i=0;i<n;i++){
		if(dp[i] > a){
			a = dp[i];
		}
	}
	for(int i=0;i<n;i++){
		if(dp[i] == a) b += dp2[i];
	}
	cout << a << " " << b*ct << "\n";
	//cout << "Count: " << ct << "\n";
	return 0;
}

Subtask #1
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 504 KB Output isn't correct
2 Incorrect 139 ms 384 KB Output isn't correct
3 Incorrect 147 ms 504 KB Output isn't correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 208 ms 396 KB Output is correct
6 Correct 308 ms 384 KB Output is correct
7 Execution timed out 1067 ms 10060 KB Time limit exceeded
8 Execution timed out 1075 ms 10048 KB Time limit exceeded
9 Execution timed out 1079 ms 10052 KB Time limit exceeded
10 Execution timed out 1076 ms 10056 KB Time limit exceeded
11 Runtime error 67 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 51 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 51 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 89 ms 2780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 94 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 118 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 80 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 73 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 80 ms 3820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 71 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)