let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

NKSEQ - Dãy số

solution.md
\[S[i] = A[1] + A[2] + ... + A[i]\]

Vị trí \(i\) không tốt nếu ít nhất 1 trong 2 điều kiện sau thỏa:

\[\exists k \geq i, S[k] - S[i-1] \leq 0\\ \exists k < i, S[k] + S[n] - S[i-1] \leq 0\]

Suy ra \(i\) là vị trí tốt nếu

\[\begin{cases} S[i-1] < S[k], \forall k \geq i\\ S[i-1] < S[k] + S[n], \forall k < i \end{cases}\]
main.cpp
Open in Github Download
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> s(n+1);
    s[0] = 0;
    for (int i=1; i<=n; i++) {
        cin >> s[i];
        s[i] += s[i-1];
    }

    vector<bool> f(n+1);
    for (int i=n, smin = s[n]; i>0; i--) {
        f[i] = s[i-1] < smin;
        smin = min(smin, s[i-1]);
    }

    vector<bool> g(n+1);
    for (int i=1, smin = s[n]; i<=n; i++) {
        g[i] = s[i-1] < smin;
        smin = min(smin, s[i] + s[n]);
    }

    int count = 0;
    for (int i=1; i<=n; i++) count += f[i] && g[i];
    cout << count;

    return 0;
}
Comments