Submission #243514

#	Time	Username	Problem	Language	Result	Execution time	Memory
243514		Vimmer	Zoltan (COCI16_zoltan)	C++14	42 / 140	983 ms	8312 KiB

zoltan

#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 / 140