oj.uz

Submission #243495

# Submission time Handle Problem Language Result Execution time Memory
243495 2020-07-01T09:09:48 Z VEGAnn Zoltan (COCI16_zoltan) C++14
14 / 140
 1000 ms 12384 KB 
#include <bits/stdc++.h>
//#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 all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
using namespace std;
const int N = 2010;
const int oo = 2e9;
const int md = int(1e9) + 7;
i2 f[N][N][2], ans, cur;
vector<int> vc;
int n, a[N];

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

void upd(i2 &cr, i2 nw){
    if (nw[0] > cr[0])
        cr = nw; else
    if (nw[0] == cr[0]){
        SUM(cr[1], nw[1]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    assert(n <= 1000);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vc.PB(a[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();

    f[0][a[0]][a[0]] = {1, 1};

    int mn = a[0], mx = a[0];

    int po = 1;

    for (int i = 1; i < n; i++){
        int tp = (i & 1);

        SUM(po, po);

        mn = min(mn, a[i]);
        mx = max(mx, a[i]);

        for (int men = mn;  men <= mx; men++)
        for (int mex = men; mex <= mx; mex++)
            f[men][mex][tp] = {0, 0};

        f[a[i]][a[i]][tp] = {1, po};

        for (int men = mn;  men <= mx; men++)
        for (int mex = men; mex <= mx; mex++){
            if (f[men][mex][0][tp ^ 1] == 0) continue;

            upd(f[men][mex][tp], f[men][mex][tp ^ 1]);
            upd(f[men][mex][tp], f[men][mex][tp ^ 1]);

            cur = f[men][mex][tp ^ 1];
            cur[0]++;

            if (a[i] < men)
                upd(f[a[i]][mex][tp], cur);

            if (a[i] > mex)
                upd(f[men][a[i]][tp], cur);
        }
    }

    int tp = ((n - 1) & 1);

    for (int i = mn; i <= mx; i++)
    for (int j = i; j <= mx; j++)
        upd(ans, f[i][j][tp]);

    cout << ans[0] << " " << ans[1];

    return 0;
}

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Correct 4 ms 384 KB Output is correct
5 Incorrect 5 ms 384 KB Output isn't correct
6 Correct 5 ms 384 KB Output is correct
7 Execution timed out 1088 ms 12384 KB Time limit exceeded
8 Execution timed out 1091 ms 12280 KB Time limit exceeded
9 Execution timed out 1091 ms 12280 KB Time limit exceeded
10 Execution timed out 1095 ms 12280 KB Time limit exceeded
11 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 10 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)