oj.uz

Submission #98514

# Submission time Handle Problem Language Result Execution time Memory
98514 2019-02-23T19:55:48 Z thiago4532 Zoltan (COCI16_zoltan) C++17
21 / 140
 1000 ms 9984 KB 
#include <bits/stdc++.h>
// #define int int64_t
#define int int64_t
 
using namespace std;
const int maxn = 1010;
int v[maxn], dp[maxn], dp2[maxn], i;
deque<int> dq;
int ct=0, n;
int qtd[maxn];

void backtracking(int i, deque<int> const& d){
	if(i == n){
		for(int i=0;i<n;i++)
			v[i] = d[i];
		memset(dp, 0, sizeof dp);
		memset(dp2, 0, sizeof dp2);

		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];
		}
		qtd[a] += b;
		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=n;i>=1;i--){
		if(qtd[i] > 0){
			cout << i << " " << (qtd[i]%(int)(1e9 + 7)) << "\n";
			return 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 841 ms 476 KB Output isn't correct
2 Incorrect 802 ms 384 KB Output isn't correct
3 Incorrect 944 ms 504 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 815 ms 384 KB Output is correct
6 Correct 527 ms 504 KB Output is correct
7 Execution timed out 1075 ms 9968 KB Time limit exceeded
8 Execution timed out 1057 ms 9984 KB Time limit exceeded
9 Execution timed out 1069 ms 9968 KB Time limit exceeded
10 Execution timed out 1078 ms 9976 KB Time limit exceeded
11 Runtime error 95 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 63 ms 2788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 54 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 109 ms 2904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 84 ms 3292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 93 ms 3768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 86 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 83 ms 3736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 99 ms 3800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 100 ms 3940 KB Execution killed with signal 11 (could be triggered by violating memory limits)