oj.uz

답안 #253653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253653 2020-07-28T13:41:46 Z NONAME Zoltan (COCI16_zoltan) C++14
21 / 140
 764 ms 2432 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = int(1e5) + 500;
const int base = int(1e9) + 7;

int n;
int fen[N], a[N], f[N], c[N];

int add(int x, int y) {
    x += y;
    if (x > base)
        x -= base;
    return x;
}

void upd(int x, int vl) { while (x < n) fen[x] = max(fen[x], vl), x = (x | (x + 1)); }
int f_max(int x) { int k = 0; while (x >= 0) k = max(k, fen[x]), x = (x & (x + 1)) - 1; return k; }

bool cmp(int x, int y) { return a[x] < a[y]; }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i], c[i] = i;
    sort(c, c + n, cmp);
    int cur = 0;
    for (int i = 1; i < n; ++i)
        if (a[c[i]] == a[c[i - 1]]) a[c[i - 1]] = cur;
            else a[c[i - 1]] = cur++;
    a[c[n - 1]] = cur;

    //mn = mx = a[0];
    //ans = 1;
    //for (int i = 1; i < n; ++i) {
        //if (a[i] < mn) ++ans, mn = a[i];
        //if (a[i] > mx) ++ans, mx = a[i];
    //}

    int ans = 0, res = 0;
    if (n <= 20) {
        for (int msk = 0; msk < (1 << (n - 1)); ++msk) {
            vector <int> l, r;
            for (int i = 1; i < n; ++i)
                if (msk & (1 << (i - 1))) r.push_back(a[i]);
                    else l.push_back(a[i]);

            reverse(l.begin(), l.end());
            vector <int> v;

            for (int i : l)
                v.push_back(i);
            v.push_back(a[0]);
            for (int i : r)
                v.push_back(i);

            for (int i = 0; i < n; ++i)
                fen[i] = 0;
            for (int i = 0; i < n; ++i) {
                f[i] = f_max(v[i] - 1) + 1;
                upd(i, f[i]);
            }

            int nans = 0;
            for (int i = 0; i < n; ++i)
                if (fen[i] > nans)
                    nans = fen[i];

            if (nans > ans)
                ans = nans, res = 0;

            for (int i = 0; i < n; ++i)
                if (fen[i] == ans)
                    res = add(res, 1);
        }
    }

    cout << ans << " " << res << "\n";
}

Subtask #1
21.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 708 ms 360 KB Output isn't correct
2 Incorrect 711 ms 384 KB Output isn't correct
3 Incorrect 764 ms 384 KB Output isn't correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 726 ms 396 KB Output is correct
6 Correct 638 ms 404 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Incorrect 35 ms 1920 KB Output isn't correct
12 Incorrect 33 ms 1792 KB Output isn't correct
13 Incorrect 29 ms 1792 KB Output isn't correct
14 Incorrect 38 ms 1792 KB Output isn't correct
15 Incorrect 48 ms 2040 KB Output isn't correct
16 Incorrect 57 ms 2432 KB Output isn't correct
17 Incorrect 45 ms 2304 KB Output isn't correct
18 Incorrect 46 ms 2296 KB Output isn't correct
19 Incorrect 46 ms 2304 KB Output isn't correct
20 Incorrect 45 ms 2296 KB Output isn't correct