Educational Codeforces Round 23D: Imbalanced Array

http://codeforces.com/contest/817/problem/D

久しぶりにコンテストに参加してみたが、全く頭が動かなかった。これくらいの問題が解けないのは大問題。コンテスト中なぜかいろいろ勘違いして最小値最大値分離出来ねえなあと思っていた。

int N;
ll A[MAX_N];
ll S[MAX_N];

ll f() {
	stack<int> s;
	ll res = 0;
	rep(i, 0, N) {
		while(!s.empty()) {
			int t = s.top();
			if(A[t] >= A[i]) s.pop();
			else break;
		}
		if(s.empty()) S[i] = (i + 1) * A[i];
		else {
			int t = s.top(); 
			S[i] = (i - t) * A[i] + S[t];
		}
		res += S[i];
		s.push(i);
	}
	return res;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	ll res = f();
	rep(i, 0, N) A[i] *= -1;
	res += f();
	cout << -res << "\n";
}

分離したらスライド最小値的なやつ。スタック使うやつもキューを使うやつと本質は同じだからスライド最小値でまとめてしまっている。