Cod sursa(job #2894749)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 28 aprilie 2022 12:11:19
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
const int mod = 666013;
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch() {
        if (++sp == 4096) {
            sp = 0, fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
public:
    InParser(const char* name) {
        fin = fopen(name, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    template<typename T>
    InParser& operator >> (T &number) {
        register T ch, sgn = 1;
        number = 0;
        while (!isdigit(ch = read_ch()) && ch != '-');
        if (ch == '-') {
            sgn = -1, ch = read_ch();
        }
        do {
            number = 10 * number + ch - '0';
        } while (isdigit(ch = read_ch()));
        number *= sgn;
        return *this;
    }
} fin("secv2.in");
ofstream fout("secv2.out");

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // Fie suma(i, j) = v[i] + v[i + 1] + ... + v[j]
    // suma(i, j) = suma(1, j) - suma(1, i - 1)
    // lungimea >= k => j - i + 1 >= k
    // => pentru j fixat, i <= j - k + 1
    //                 => i - 1 <= j - k
    // Precalculam sumele partiale si minime partiale
    // pe sume partiale iar raspunsul pentru capatul drept
    // fixat in j (j >= k) este s[j] - mn[j - k]
    int n, k;
    fin >> n >> k;
    vector<int> v(n + 1), s(n + 1), mn(n + 1);
    // mn[i] = indicele j, 1 <= j <= i, s[j] minim
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        s[i] = s[i - 1] + v[i];
        mn[i] = s[mn[i - 1]] < s[i] ? mn[i - 1] : i;
    }
    int dr = k;
    for (int i = k; i <= n; ++i) {
        if (s[dr] - s[mn[dr - k]] < s[i] - s[mn[i - k]]) {
            dr = i;
        }
    }
    fout << mn[dr - k] + 1 << ' ' << dr << ' ' << s[dr] - s[mn[dr - k]];
}