99802024-03-22 17:37:28abelke2Leggyorsabb pénzkeresés (50)cpp17Accepted 50/5035ms15860 KiB
#include <iostream>
#include <vector>

void kiirVektor(std::vector<int> vek) {
    for (int i : vek) {
        std::cout << i << " ";
    }
    std::cout << "\n------------------\n";
}

void beolvas(int& n, int& penztOsszeszedni, std::vector<int>& napok) {
    std::cin >> n >> penztOsszeszedni;
    napok.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> napok[i];
    }
}

int megold(int n, int penztOsszeszedni, std::vector<int> napok) {
    std::vector<int>addigMennyit = std::vector<int>(n);
    addigMennyit[0] = napok[0];
    for (int i = 1; i < n; ++i) {
        addigMennyit[i] = addigMennyit[i - 1] + napok[i];
    }
    //kiirVektor(addigMennyit);

    //Ket indexet hasznalva az intervallumokat linearis idoben ellenorizzuk
    int szam = 0;
    int i = 0;
    int j = 0;
    //Elnavigalunk a sorrendben elso (nem feltetlen optimalis) megoldashoz
    while (j < n && addigMennyit[j] < penztOsszeszedni) {
        ++j;
    }
    szam = j - i + 1;

    while (j < n && i < n - 1) {
        //Lepunk egyet a bal oldali indexszel jobbra. Ha ezzel jobb megoldast talalunk, azt megjegyezzuk, ellenkezo
        //esetben jobb indexszel lepunk jobbra
        int elotte = -1;
        if (i >= 1) {
            elotte = addigMennyit[i - 1];
        }
        else {
            elotte = 0;
        }
        if (i + 1 <= j && addigMennyit[j] - addigMennyit[i] >= penztOsszeszedni) {
            ++i;
            if (j - i + 1 < szam) {
                szam = j - i + 1;
            }
        }
        else if(j < n) {
            ++j;
        }
        else {
            ++i;
        }
    }
    return szam;
}

int main() {
    int n = 0;
    int penztOsszeszedni = 0;
    std::vector<int>napok;
    beolvas(n, penztOsszeszedni, napok);

    int megoldas = megold(n, penztOsszeszedni, napok);
    std::cout << megoldas;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1808 KiB
2Accepted0/035ms4788 KiB
3Accepted2/23ms2844 KiB
4Accepted2/23ms2788 KiB
5Accepted2/23ms3028 KiB
6Accepted2/26ms3484 KiB
7Accepted2/26ms3580 KiB
8Accepted2/26ms3756 KiB
9Accepted2/26ms3892 KiB
10Accepted2/26ms4064 KiB
11Accepted2/235ms6736 KiB
12Accepted2/235ms7452 KiB
13Accepted2/235ms8176 KiB
14Accepted2/235ms8752 KiB
15Accepted2/235ms9288 KiB
16Accepted2/235ms10008 KiB
17Accepted2/235ms10460 KiB
18Accepted2/235ms10940 KiB
19Accepted2/235ms11552 KiB
20Accepted2/235ms12116 KiB
21Accepted2/235ms12744 KiB
22Accepted2/235ms13208 KiB
23Accepted2/235ms13624 KiB
24Accepted2/235ms14104 KiB
25Accepted2/235ms14712 KiB
26Accepted2/235ms15280 KiB
27Accepted2/235ms15860 KiB