Submission #243488

#	Time	Username	Problem	Language	Result	Execution time	Memory
243488		Vimmer	Zoltan (COCI16_zoltan)	C++14	21 / 140	1097 ms	3188 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;

ll 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]);

        for (int i = 0; i < n; i++)
        {
            ll kol = 1, len = 1;

            int j = i;

            while (1)
            {
                int val = gr[j];

                j++;

                while (j < sz(gr) && gr[j] <= val) j++;

                if (j == sz(gr)) break;

                val = gr[j];

                len++;

                while (j + 1 != sz(gr) && gr[j + 1] <= val) {j++; if (gr[j] == val) kol = (kol + kol) % M;}
            }

            sum[len] += kol; sum[len] %= M;

            mx = max(mx, len);
        }
    }

    cout << mx << " " << sum[mx] << endl;
}

• Subtask 1: 21 / 140