oj.uz

Submission #892787

# Submission time Handle Problem Language Result Execution time Memory
892787 2023-12-26T00:40:28 Z ayalla Feast (NOI19_feast) C++14
22 / 100
 141 ms 12572 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long int
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 300005
#define mod 998244353

int n, k;
int a[MAXN];

pi solve(int lambda)
{
  vector<int> dp(n + 1);
  vector<int> cnt(n + 1);
  dp[0] = 0;
  cnt[0] = 0;
  pi best = {0, 0};
  pi curr = {0, 0};
  auto f = [&](pi x)
  {
    return dp[x.fir] + x.sec;
  };
  for (int i = 1; i <= n; i++)
  {
    dp[i] = dp[i - 1];
    cnt[i] = cnt[i - 1];
    int id = i - 1;
    best.sec += a[id];
    if (f(best) < f({i, a[id]}))
    {
      best = {i, a[id]};
    }
    int s = dp[best.fir] + best.sec - lambda;
    if (s > dp[i])
    {
      dp[i] = s;
      cnt[i] = cnt[best.fir] + 1;
    }
  }
  return {dp[n], cnt[n]};
}
int aliens_trick()
{
  int l = 0, r = 1e15;
  while (l < r)
  {
    int mid = (l + r) >> 1;
    pi ans = solve(mid);
    (ans.sec > k) ? l = mid + 1 : r = mid;
  }
  pi ans = solve(l);
  return ans.fir + (l * k);
}
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cout << aliens_trick() << endl;
  return 0;
}

Compilation message

feast.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
feast.cpp:29:6: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
   29 |   pi curr = {0, 0};
      |      ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 10188 KB Output is correct
2 Correct 108 ms 10356 KB Output is correct
3 Correct 108 ms 10500 KB Output is correct
4 Correct 109 ms 10388 KB Output is correct
5 Correct 108 ms 10356 KB Output is correct
6 Correct 69 ms 10172 KB Output is correct
7 Correct 107 ms 10264 KB Output is correct
8 Correct 89 ms 10428 KB Output is correct
9 Correct 90 ms 10320 KB Output is correct
10 Correct 108 ms 10296 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 8544 KB Output is correct
2 Correct 104 ms 8800 KB Output is correct
3 Correct 101 ms 8816 KB Output is correct
4 Incorrect 83 ms 8808 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 132 ms 10556 KB Output is correct
2 Correct 129 ms 10404 KB Output is correct
3 Correct 113 ms 10508 KB Output is correct
4 Correct 112 ms 10432 KB Output is correct
5 Correct 116 ms 10756 KB Output is correct
6 Correct 141 ms 12572 KB Output is correct
7 Correct 137 ms 10544 KB Output is correct
8 Correct 114 ms 10544 KB Output is correct
9 Correct 140 ms 10984 KB Output is correct
10 Correct 138 ms 10612 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 10188 KB Output is correct
2 Correct 108 ms 10356 KB Output is correct
3 Correct 108 ms 10500 KB Output is correct
4 Correct 109 ms 10388 KB Output is correct
5 Correct 108 ms 10356 KB Output is correct
6 Correct 69 ms 10172 KB Output is correct
7 Correct 107 ms 10264 KB Output is correct
8 Correct 89 ms 10428 KB Output is correct
9 Correct 90 ms 10320 KB Output is correct
10 Correct 108 ms 10296 KB Output is correct
11 Correct 104 ms 8544 KB Output is correct
12 Correct 104 ms 8800 KB Output is correct
13 Correct 101 ms 8816 KB Output is correct
14 Incorrect 83 ms 8808 KB Output isn't correct
15 Halted 0 ms 0 KB -