Submission #229994

#	Time	Username	Problem	Language	Result	Execution time	Memory
229994		osaaateiasavtnl	Zoltan (COCI16_zoltan)	C++14	70 / 140	1099 ms	4472 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7, MOD = 1000 * 1000 * 1000 + 7;
int a[N], l[N], r[N], cntl[N], cntr[N], pw[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = (pw[i - 1] * 2) % MOD;

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int len = 0;
    for (int i = n; i; --i) {
        l[i] = r[i] = cntl[i] = cntr[i] = 1;
        for (int j = i + 1; j <= n; ++j) {
            if (a[j] < a[i]) {
                if (l[j] + 1 > l[i]) {
                    l[i] = l[j] + 1;
                    cntl[i] = cntl[j];
                }   
                else if (l[j] + 1 == l[i]) {
                    cntl[i] = (cntl[i] + cntl[j]) % MOD;
                }   
            }   
        }   
        for (int j = i + 1; j <= n; ++j) {
            if (a[j] > a[i]) {
                if (r[j] + 1 > r[i]) {
                    r[i] = r[j] + 1;
                    cntr[i] = cntr[j] % MOD;
                }   
                else if (r[j] + 1 == r[i]) {
                    cntr[i] = (cntr[i] + cntr[j]) % MOD;
                }   
            }   
        }   
        len = max(len, l[i] + r[i] - 1);
    }   

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (l[i] + r[i] - 1 == len) {
            ans += (cntl[i] * cntr[i]) % MOD;
            ans %= MOD;
        }   
    }
    ans = ans * pw[n - len] % MOD;

    cout << len << ' ' << ans << endl;
}

• Subtask 1: 70 / 140