#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 100010
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int sum[N], mx, a[N];
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int msk = 0; msk < (1 << n); msk++)
{
if (msk & 1) continue;
vector <int> gr; gr.clear();
for (int i = n - 1; i >= 0; i--)
if ((1 << i) & msk) gr.pb(a[i]);
for (int i = 0; i < n; i++)
if (!((1 << i) & msk)) gr.pb(a[i]);
pair <int, int> f[n][n];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; i++) f[i][i] = {1, 1};
for (int i = 0; i < n - 1; i++)
for (int j = 0; j <= i; j++)
{
if (f[i][j].S == 0) continue;
mx = max(mx, f[i][j].F);
if (i == j) sum[f[i][j].F] = (sum[f[i][j].F] + f[i][j].S) % M;
if (f[i + 1][j].F < f[i][j].F) f[i + 1][j] = f[i][j];
else if (f[i + 1][j].F == f[i][j].F) f[i + 1][j].S = (f[i + 1][j].S + f[i][j].S) % M;
if (gr[j] < gr[i + 1])
{
int len = f[i][j].F + 1;
int val = f[i][j].S;
if (f[i + 1][i + 1].F < len) f[i + 1][i + 1] = {len, val};
else if (f[i + 1][i + 1].F == len) f[i + 1][i + 1].S = (f[i + 1][i + 1].S + val) % M;
}
}
int nm = f[n - 1][n - 1].F; sum[nm] = (sum[nm] + f[n - 1][n - 1].S) % M; mx = max(mx, nm);
}
cout << mx << " " << sum[mx] << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
976 ms |
384 KB |
Output is correct |
| 2 |
Correct |
983 ms |
504 KB |
Output is correct |
| 3 |
Correct |
970 ms |
504 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
775 ms |
504 KB |
Output is correct |
| 6 |
Correct |
668 ms |
504 KB |
Output is correct |
| 7 |
Incorrect |
514 ms |
8192 KB |
Output isn't correct |
| 8 |
Incorrect |
589 ms |
8192 KB |
Output isn't correct |
| 9 |
Incorrect |
475 ms |
8312 KB |
Output isn't correct |
| 10 |
Incorrect |
471 ms |
8312 KB |
Output isn't correct |
| 11 |
Runtime error |
30 ms |
3312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
26 ms |
3064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
25 ms |
2804 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
27 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
33 ms |
3440 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
37 ms |
3824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
32 ms |
3952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
31 ms |
3952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
31 ms |
3952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
31 ms |
3952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
