Cod sursa(job #3138501)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 19 iunie 2023 21:40:36
Problema Secventa 2 Scor 0
Compilator c-64 Status done
Runda concurs_bicli Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
int sp[MAXN], v[MAXN], poz[MAXN];
int main()
{
    FILE *fin, *fout;
    int n, k, i, max, p, u;
    //voi face un vector de sume partiale
    //la fiecare nr voi cauta nr din dreapta lui care are suma partiala maxima
    //ca sa gasesc care nr are suma partiala maxima, voi tine intr-un vector
    //la v[i] care este cel mai mare nr din dreapta lui i
    //si in poz[i] este pozitia acelui nr maxim
    fin = fopen("secv2.in", "r");
    fscanf(fin, "%d%d%d", &n, &k, &sp[0]);
    v[0] = sp[0];
    for (i = 1; i < n; i++) {
        fscanf(fin, "%d", &v[i]);//la inceput in v sunt nr initiale
        sp[i] = sp[i - 1] + v[i];
    }
    fclose(fin);
    max = p = -1;
    for (i = n - 1; i >= k - 1; i--) {
        if (v[i] > max) {
            max = v[i];
            p = i;
        }
        v[i - k + 1] = max;
        poz[i - k + 1] = p;
    }
    max = v[0];
    //acum p este primul si u este ultimul
    p = 0;
    u = poz[0];
    for (i = 1; i <= n - k; i++) {
        if (v[i] - sp[i - 1] > max) {
            max = v[i] - sp[i - 1];
            p = i;
            u = poz[i];
        }
    }
    fout = fopen("secv2.out", "w");
    fprintf(fout, "%d %d %d\n", p + 1, u + 1, max);
    fclose(fout);
    return 0;
}