oj.uz

답안 #98508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98508 2019-02-23T19:49:36 Z thiago4532 Zoltan (COCI16_zoltan) C++17
21 / 140
 1000 ms 9948 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;
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] << "\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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 896 ms 428 KB Output isn't correct
2 Incorrect 901 ms 424 KB Output isn't correct
3 Incorrect 822 ms 428 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 849 ms 412 KB Output is correct
6 Correct 616 ms 412 KB Output is correct
7 Execution timed out 1044 ms 9932 KB Time limit exceeded
8 Execution timed out 1040 ms 9944 KB Time limit exceeded
9 Execution timed out 1056 ms 9920 KB Time limit exceeded
10 Execution timed out 1072 ms 9948 KB Time limit exceeded
11 Runtime error 70 ms 3136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 62 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 49 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 108 ms 2716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 78 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 107 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 79 ms 3740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 110 ms 3804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 98 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 70 ms 3856 KB Execution killed with signal 11 (could be triggered by violating memory limits)