http://codeforces.com/contest/425/problem/A

枚举区间左右端点,然后把区间外最大的元素与区间内最小的元素交换即可。

/*108ms,12KB*/

const int mx = 205;

int a[mx], b[mx], c[mx];

int main()
{
    int n, k, i, j, ans = -inf, l, r, kk, x, y;
    SII(n, k);
    SA(a, i, n);
    For(l, n) Forr(r, l + 1, n + 1) /// 左闭右开区间
 {
        copy(a + l, a + r, b);
        copy(a, a + l, c), copy(a + r, a + n, c + l);
        x = r - l, y = n - x;
        sort(b, b + x);
        sort(c, c + y);
        for (kk = 0, i = 0, j = y - 1; kk < k && i < x && j >= 0 && b[i] < c[j]; ++kk, ++i, --j)
            swap(b[i], c[j]);
        ans = max(ans, Acc(b, x));
    }
    PI(ans);
    return 0;
}

Comments

comments powered by Disqus