Submission #1175631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175631		Nomio	Zoltan (COCI16_zoltan)	C++20	42 / 140	1096 ms	6588 KiB

zoltan

#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll mx = 0, cnt = 0;
	for(int i = 0; i < (1 << (n - 1)); i++) {
		pair<int, ll> dp[n];
		for(int j = 0; j < n; j++) {
			dp[j] = {1, 1};
		}
		vector<int> v, vec;
		for(int j = 0; j < n - 1; j++) {
			if((i >> j) % 2 == 1) v.push_back(a[j + 1]);
			else vec.push_back(a[j + 1]);
		}
		reverse(v.begin(), v.end());
		v.push_back(a[0]);
		for(int x : vec) {
			v.push_back(x);
		}
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < j; k++) {
				if(v[j] > v[k]) {
					if(dp[k].f + 1 == dp[j].f) dp[j].s += dp[k].s;
					else if(dp[k].f + 1 > dp[j].f) dp[j] = {dp[k].f + 1, dp[k].s};
					dp[j].s %= mod;
				}
			}
			if(dp[j].f > mx) {
				mx = dp[j].f;
				cnt = dp[j].s;
			} else if(dp[j].f == mx) {
				cnt += dp[j].s;
			}
			cnt %= mod;
		}
	}
	cout << mx << ' ' << cnt << '\n';
	return 0;
}

• Subtask 1: 42 / 140