oj.uz

Submission #229994

# Submission time Handle Problem Language Result Execution time Memory
229994 2020-05-07T14:37:38 Z osaaateiasavtnl Zoltan (COCI16_zoltan) C++14
70 / 140
 1000 ms 4472 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Correct 6 ms 1920 KB Output is correct
3 Correct 6 ms 1920 KB Output is correct
4 Correct 7 ms 2048 KB Output is correct
5 Correct 7 ms 1920 KB Output is correct
6 Correct 6 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 10 ms 2048 KB Output is correct
9 Correct 10 ms 1920 KB Output is correct
10 Correct 9 ms 1920 KB Output is correct
11 Execution timed out 1084 ms 3704 KB Time limit exceeded
12 Execution timed out 1095 ms 3576 KB Time limit exceeded
13 Execution timed out 1099 ms 3448 KB Time limit exceeded
14 Execution timed out 1097 ms 3576 KB Time limit exceeded
15 Execution timed out 1062 ms 3960 KB Time limit exceeded
16 Execution timed out 1094 ms 4188 KB Time limit exceeded
17 Execution timed out 1077 ms 4472 KB Time limit exceeded
18 Execution timed out 1095 ms 4364 KB Time limit exceeded
19 Execution timed out 1078 ms 4380 KB Time limit exceeded
20 Execution timed out 1092 ms 4468 KB Time limit exceeded