oj.uz

Submission #856512

# Submission time Handle Problem Language Result Execution time Memory
856512 2023-10-03T18:49:35 Z ArminAzimi Zoltan (COCI16_zoltan) C++14
0 / 140
 3 ms 636 KB 
#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;

    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 = 0;
        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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 3 ms 348 KB Output isn't correct
8 Incorrect 3 ms 348 KB Output isn't correct
9 Incorrect 3 ms 484 KB Output isn't correct
10 Incorrect 3 ms 484 KB Output isn't correct
11 Runtime error 1 ms 600 KB Execution killed with signal 11
12 Runtime error 1 ms 600 KB Execution killed with signal 11
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Runtime error 1 ms 604 KB Execution killed with signal 11
15 Runtime error 1 ms 604 KB Execution killed with signal 11
16 Runtime error 1 ms 604 KB Execution killed with signal 11
17 Runtime error 1 ms 600 KB Execution killed with signal 11
18 Runtime error 1 ms 604 KB Execution killed with signal 11
19 Runtime error 1 ms 636 KB Execution killed with signal 11
20 Runtime error 1 ms 604 KB Execution killed with signal 11