oj.uz

Submission #243488

# Submission time Handle Problem Language Result Execution time Memory
243488 2020-07-01T09:01:59 Z Vimmer Zoltan (COCI16_zoltan) C++14
21 / 140
 1000 ms 3188 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;

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 510 ms 504 KB Output isn't correct
2 Incorrect 517 ms 384 KB Output isn't correct
3 Incorrect 515 ms 504 KB Output isn't correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 475 ms 504 KB Output is correct
6 Correct 382 ms 384 KB Output is correct
7 Incorrect 53 ms 504 KB Output isn't correct
8 Incorrect 54 ms 384 KB Output isn't correct
9 Incorrect 52 ms 384 KB Output isn't correct
10 Incorrect 50 ms 384 KB Output isn't correct
11 Execution timed out 1095 ms 2684 KB Time limit exceeded
12 Execution timed out 1093 ms 2556 KB Time limit exceeded
13 Execution timed out 1096 ms 2292 KB Time limit exceeded
14 Execution timed out 1093 ms 2556 KB Time limit exceeded
15 Execution timed out 1097 ms 2812 KB Time limit exceeded
16 Execution timed out 1091 ms 3068 KB Time limit exceeded
17 Execution timed out 1097 ms 3060 KB Time limit exceeded
18 Execution timed out 1093 ms 3068 KB Time limit exceeded
19 Execution timed out 1091 ms 3188 KB Time limit exceeded
20 Execution timed out 1093 ms 3068 KB Time limit exceeded