oj.uz

Submission #243511

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

        pair <ll, ll> 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])
                {
                    ll len = f[i][j].F + 1;

                    ll 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;
                }
            }

        ll 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
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 384 KB Time limit exceeded
2 Execution timed out 1094 ms 384 KB Time limit exceeded
3 Execution timed out 1094 ms 384 KB Time limit exceeded
4 Correct 5 ms 384 KB Output is correct
5 Correct 967 ms 504 KB Output is correct
6 Correct 845 ms 504 KB Output is correct
7 Incorrect 910 ms 16096 KB Output isn't correct
8 Incorrect 791 ms 16124 KB Output isn't correct
9 Incorrect 816 ms 16064 KB Output isn't correct
10 Incorrect 819 ms 16000 KB Output isn't correct
11 Runtime error 39 ms 4720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 26 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 30 ms 3828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 26 ms 4080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 34 ms 4848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 38 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 32 ms 5616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 31 ms 5600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 32 ms 5488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 39 ms 5592 KB Execution killed with signal 11 (could be triggered by violating memory limits)