fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. long long minSum(vector<int> a) {
  6. 	// для удобства добавим в начало массива ноль
  7. 	a.insert(a.begin(), 0);
  8. 	// элементы массива индексируются [1..n]
  9. 	int n = a.size() - 1;
  10.  
  11. 	// префиксные суммы
  12. 	// cumsum[k] := a[1] + ... + a[k]
  13. 	vector<ll> prefixSums;
  14. 	for (int ai : a)
  15. 		prefixSums.push_back(prefixSums.empty() ? 0 : prefixSums.back() + ai);
  16.  
  17. 	// сумма на отрезке a_j ... a_i равна сумме на префиксе [1..i] минус сумме на префиксе [1..j-1]
  18. 	// по условию задачи рассматриваются только такие суммы, что a_j == a_i
  19. 	// будем итерироваться по массиву и для каждого числа a_j запоминать минимальную сумму на префиксе [1..j-1]
  20. 	// при встрече очередного числа a_i будем обновлять ответ, рассматривая отрезок [j..i]
  21. 	unordered_map<int, ll> numberToMinSum;
  22. 	ll answer = numeric_limits<ll>::min();
  23. 	for (int i = 1; i <= n; ++i) {
  24. 		if (numberToMinSum.find(a[i]) != numberToMinSum.end()) {
  25. 			numberToMinSum[a[i]] = min(numberToMinSum[a[i]], prefixSums[i - 1]);
  26. 			answer = max(answer, prefixSums[i] - numberToMinSum[a[i]]);
  27. 		} else {
  28. 			numberToMinSum[a[i]] = prefixSums[i - 1];
  29. 		}
  30. 	}
  31. 	return answer;
  32. }
  33.  
  34. void test(vector<int> a) {
  35. 	cout << "вектор:";
  36. 	for (int ai : a)
  37. 		cout << " " << ai;
  38.  
  39. 	cout << ", сумма: " << minSum(a) << endl;
  40. }
  41.  
  42. int main() {
  43. 	test({3, 5, 6, 3, 5});
  44. 	test({-1, -1, -1});
  45. 	return 0;
  46. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
вектор: 3 5 6 3 5, сумма: 19
вектор: -1 -1 -1, сумма: -1
https://ideone.com/st01LP
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!