oj.uz

Submission #833138

# Submission time Handle Problem Language Result Execution time Memory
833138 2023-08-22T02:12:14 Z veehz Feast (NOI19_feast) C++17
22 / 100
 112 ms 2688 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back

int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  // subtask 1 a_i > 0
  if (*min_element(a.begin(), a.end()) >= 0) {
    cout << accumulate(a.begin(), a.end(), 0LL) << endl;
    return 0;
  }

  // subtask 2 at most one a_i < 0
  if (count_if(a.begin(), a.end(), [](ll x) { return x < 0; }) <= 1) {
    int pos = find_if(a.begin(), a.end(), [](ll x) { return x < 0; }) - a.begin();
    ll mx = 0;
    mx = max(mx, accumulate(a.begin(), a.begin() + pos, 0LL));
    mx = max(mx, accumulate(a.begin() + pos + 1, a.end(), 0LL));
    mx = max(mx, accumulate(a.begin(), a.end(), 0LL));
    cout << mx << endl;
    return 0;
  }

  // subtask 3 K = 1, maximum subarray
  if(k == 1){
    ll mx = 0, cur = 0;
    for(int i = 0; i < n; i++){
      cur += a[i];
      mx = max(mx, cur);
      cur = max(cur, 0LL);
    }
    cout << mx << endl;
    return 0;
  }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 2560 KB Output is correct
2 Correct 81 ms 2516 KB Output is correct
3 Correct 83 ms 2644 KB Output is correct
4 Correct 85 ms 2620 KB Output is correct
5 Correct 104 ms 2600 KB Output is correct
6 Correct 82 ms 2688 KB Output is correct
7 Correct 82 ms 2560 KB Output is correct
8 Correct 84 ms 2516 KB Output is correct
9 Correct 84 ms 2516 KB Output is correct
10 Correct 87 ms 2604 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2576 KB Output is correct
2 Correct 46 ms 2644 KB Output is correct
3 Correct 49 ms 2516 KB Output is correct
4 Incorrect 46 ms 2564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 2612 KB Output is correct
2 Correct 88 ms 2516 KB Output is correct
3 Correct 89 ms 2516 KB Output is correct
4 Correct 88 ms 2584 KB Output is correct
5 Correct 91 ms 2600 KB Output is correct
6 Correct 89 ms 2620 KB Output is correct
7 Correct 90 ms 2624 KB Output is correct
8 Correct 112 ms 2608 KB Output is correct
9 Correct 95 ms 2644 KB Output is correct
10 Correct 105 ms 2644 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 2560 KB Output is correct
2 Correct 81 ms 2516 KB Output is correct
3 Correct 83 ms 2644 KB Output is correct
4 Correct 85 ms 2620 KB Output is correct
5 Correct 104 ms 2600 KB Output is correct
6 Correct 82 ms 2688 KB Output is correct
7 Correct 82 ms 2560 KB Output is correct
8 Correct 84 ms 2516 KB Output is correct
9 Correct 84 ms 2516 KB Output is correct
10 Correct 87 ms 2604 KB Output is correct
11 Correct 49 ms 2576 KB Output is correct
12 Correct 46 ms 2644 KB Output is correct
13 Correct 49 ms 2516 KB Output is correct
14 Incorrect 46 ms 2564 KB Output isn't correct
15 Halted 0 ms 0 KB -