1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long values[1000001];

long ways(long, long, long);

int main() {
    long n;
    cin >> n;
    long leftguard = 0;
    long rightguard = n-1;
    for (long i = 0; i < n; ++i) {
        cin >> values[i];
    }
    long totalsum = 0;
    for (long i = 0; i < n; ++i) {
        // values higher than min_untakeable must be left for optimal score
        long untaken = n - i;
        long min_untakeable = n - (untaken / 2);
        // cerr << "CUTTING OUT " << i << endl;
        // cerr << "MUST LEAVE TOP " << untaken << " VALUES" << endl;
        // cerr << "(MUST LEAVE FROM " << min_untakeable << " UP)" <<endl;
        while (values[leftguard] < min_untakeable) {
            leftguard++;
        }
        while (values[rightguard] < min_untakeable) {
            rightguard--;
        }
        // cerr << "LEFT POSSIBILITIES: " << leftguard << endl;
        // cerr << "RIGHT POSSIBILITIES: " << (n - 1 - rightguard) << endl;
        // cerr << "CAN ACHIEVE " << i << " IN " << ways(i, leftguard, (n - 1 - rightguard)) << " WAYS." << endl;
        totalsum += ways(i, leftguard, (n - 1 - rightguard));
    }
    // cerr << "--------------------------------------------" << endl;
    cout << 2*n+1 << " " << totalsum << endl;
    return 0;
}

long ways(long target, long leftpart, long rightpart) {
    // in how many ways can we get a sum of target from a+b, where a <= leftpart and b <= rightpart?
    if (leftpart + rightpart < target) {
        return 0;
    } else {
        long upper = max(leftpart, rightpart);
        long lower = min(leftpart, rightpart);
        if (target <= lower) {
            return target + 1;
        }
        if (target > upper) {
            // target > upper >= lower
            return lower + upper - target + 1;
        } else {
            // upper >= target > lower
            return lower + 1;
        }
    }
}