oj.uz

Submission #243514

# Submission time Handle Problem Language Result Execution time Memory
243514 2020-07-01T09:24:09 Z Vimmer Zoltan (COCI16_zoltan) C++14
42 / 140
 983 ms 8312 KB 
#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;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory 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)