Rezultati

Up. imeNalogaJezikRezultatČas oddaje
Aquasonic-2018 Priprava naloge C++ 100/100OK 19. apr '18 @ 18:32

Test Točke Porabljen spomin Porabljen čas Status
#1 11/11 4,742 MiB 0,071 s OK
#2 11/11 4,539 MiB 0,065 s OK
#3 11/11 4,742 MiB 0,089 s OK
#4 11/11 4,535 MiB 0,065 s OK
#5 11/11 4,539 MiB 0,078 s OK
#6 11/11 4,738 MiB 0,066 s OK
#7 11/11 3,020 MiB 0,000 s OK
#8 11/11 4,535 MiB 0,046 s OK
#9 12/12 3,023 MiB 0,000 s OK

Ocenjevani program (main.cpp):
#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define pb push_back

#define left(x) ((x) << 1)
#define right(x) ((x) << 1 | 1)
#define mid(x, y) ((x) + (y) >> 1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1 * 1e5 + 17;

ll ans = 1LL << 50;
int l, r;
int N, M;
ll TRSQ[maxn], CRSQ[maxn];

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> M >> N;

    for (int i = 1; i <= N; i++) {
        ll x, y; cin >> x >> y;
        TRSQ[i] = TRSQ[i - 1] + x;
        CRSQ[i] = CRSQ[i - 1] + y;
    }
    
    l = 1;
    r = 1;

    while (l <= N) {
        while (r < N && TRSQ[r] - TRSQ[l - 1] < M) r++;

        if (TRSQ[r] - TRSQ[l - 1] >= M)
            ans = min(ans, CRSQ[r] - CRSQ[l - 1]);

        l++;
        while (r > l && TRSQ[r] - TRSQ[l - 1] >= M) r--;
    }

    if (ans == (1LL << 50)) puts("Tekma bo polom"), exit(0);

    cout << CRSQ[N] - ans << endl;


    return 0;
}