Submission #856518

#	Time	Username	Problem	Language	Result	Execution time	Memory
856518		ArminAzimi	Zoltan (COCI16_zoltan)	C++14	70 / 140	3 ms	348 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair <int, int>, null_type,less<pair <int, int>>, rb_tree_tag,tree_order_statistics_node_update> 

const int MAXN = 1e3 + 10, MAXM = 1e2 + 10, MOD = 1000000000 + 7, MOD1 = 1e9 + 9, SQ = 350;
const long long INF = 1e9 + 11;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[MAXN], dp[MAXN][2], cnt[MAXN][2], p2[MAXN];

void solve() {
    int n;
    cin >> n;

    if (n > 1000)
        return;

    p2[0] = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p2[i + 1] = 2ll * p2[i] % MOD;
    }

    
    for (int i = n - 1; i >= 0; i--) {
        int mx = 0;
        int cnt1 = 1;
        for (int j = i + 1; j < n; j++) {
            if (a[i] < a[j]) {
                if (mx < dp[j][0]) {
                    mx = dp[j][0];
                    cnt1 = cnt[j][0];
                }
                else if (mx == dp[j][0]) {
                    cnt1 = (cnt1 + cnt[j][0]) % MOD;
                }
            }
        }

        dp[i][0] = mx + 1;
        cnt[i][0] = cnt1;
        
        mx = 0;
        cnt1 = 1;
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                if (mx < dp[j][1]) {
                    mx = dp[j][1];
                    cnt1 = cnt[j][1];
                }
                else if (mx == dp[j][1]) {
                    cnt1 = (cnt1 + cnt[j][1]) % MOD;
                }
            }
        }

        dp[i][1] = mx + 1;
        cnt[i][1] = cnt1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i][0] + dp[i][1] - 1);
    }

    int ans1 = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i][0] + dp[i][1] - 1 == ans) {
            int tmp = 1ll * cnt[i][0] * cnt[i][1] % MOD;
            tmp = 1ll * tmp * p2[n - ans] % MOD;

            ans1 = (ans1 + tmp) % MOD;
        }
    }

    cout << ans << " " << ans1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    // cin >> q;
    
    while (q--) {
        solve();
    }
}

• Subtask 1: 70 / 140