5635 2023. 08. 30 18:31:59 TomaSajt Vásárlás (75 pont) cpp17 Elfogadva 75/75 25ms 6788 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0), ios::sync_with_stdio(0);

  int n;
  cin >> n;

  vector<int> a(n), b(n), d(n);
  for (int& ai : a) cin >> ai;
  for (int& bi : b) cin >> bi;
  for (int i = 0; i < n; i++) d[i] = b[i] - a[i];

  int best_d_sum = 0, best_l = 0, best_r = -1;
  int d_sum = 0, l = 0;
  for (int r = 0; r < n; r++) {
    if (d_sum + d[r] <= 0) {
      l = r + 1;
      d_sum = 0;
    }
    else {
      d_sum += d[r];
      if (best_d_sum < d_sum) {
        best_d_sum = d_sum;
        best_l = l;
        best_r = r;
      }
    }
  }

  int res = 0;
  for (int i = 0; i < n; i++) {
    if (best_l <= i && i <= best_r)
      res += a[i];
    else
      res += b[i];
  }

  cout << res;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 75/75
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 14ms 3260 KiB
3 Elfogadva 3/3 3ms 2268 KiB
4 Elfogadva 4/4 3ms 2444 KiB
5 Elfogadva 4/4 3ms 2660 KiB
6 Elfogadva 4/4 3ms 2752 KiB
7 Elfogadva 4/4 3ms 2876 KiB
8 Elfogadva 3/3 3ms 2980 KiB
9 Elfogadva 4/4 3ms 3340 KiB
10 Elfogadva 4/4 3ms 3544 KiB
11 Elfogadva 4/4 3ms 3880 KiB
12 Elfogadva 5/5 3ms 3832 KiB
13 Elfogadva 3/3 25ms 6060 KiB
14 Elfogadva 3/3 25ms 6268 KiB
15 Elfogadva 3/3 25ms 6152 KiB
16 Elfogadva 3/3 25ms 6036 KiB
17 Elfogadva 3/3 24ms 5952 KiB
18 Elfogadva 3/3 24ms 5952 KiB
19 Elfogadva 3/3 24ms 6204 KiB
20 Elfogadva 3/3 24ms 6164 KiB
21 Elfogadva 3/3 24ms 6468 KiB
22 Elfogadva 3/3 19ms 6788 KiB
23 Elfogadva 3/3 25ms 6624 KiB
24 Elfogadva 3/3 24ms 6632 KiB