답안 #892794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892794	2023-12-26T01:52:54 Z	ayalla	Feast (NOI19_feast)	C++14	100 / 100	165 ms	9552 KB

feast

#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 - 1, a[id]}))
    {
      best = {i - 1, a[id]};
    }
    else if (f(best) == f({i - 1, a[id]}) && cnt[best.fir] > cnt[i - 1])
    {
      best = {i - 1, 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 * ans.sec);
}
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

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	7392 KB	Output is correct
2	Correct	110 ms	7552 KB	Output is correct
3	Correct	110 ms	7716 KB	Output is correct
4	Correct	72 ms	7516 KB	Output is correct
5	Correct	92 ms	7744 KB	Output is correct
6	Correct	105 ms	7432 KB	Output is correct
7	Correct	107 ms	9316 KB	Output is correct
8	Correct	110 ms	7680 KB	Output is correct
9	Correct	106 ms	7428 KB	Output is correct
10	Correct	113 ms	7576 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	7456 KB	Output is correct
2	Correct	104 ms	7624 KB	Output is correct
3	Correct	102 ms	7612 KB	Output is correct
4	Correct	104 ms	7516 KB	Output is correct
5	Correct	90 ms	7512 KB	Output is correct
6	Correct	103 ms	7504 KB	Output is correct
7	Correct	106 ms	7612 KB	Output is correct
8	Correct	71 ms	7592 KB	Output is correct
9	Correct	69 ms	7400 KB	Output is correct
10	Correct	86 ms	7648 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	132 ms	7516 KB	Output is correct
2	Correct	135 ms	7640 KB	Output is correct
3	Correct	126 ms	7504 KB	Output is correct
4	Correct	130 ms	7412 KB	Output is correct
5	Correct	132 ms	7460 KB	Output is correct
6	Correct	139 ms	7756 KB	Output is correct
7	Correct	133 ms	7540 KB	Output is correct
8	Correct	93 ms	7444 KB	Output is correct
9	Correct	132 ms	7556 KB	Output is correct
10	Correct	141 ms	7644 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	344 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	344 KB	Output is correct

Subtask #7
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	7392 KB	Output is correct
2	Correct	110 ms	7552 KB	Output is correct
3	Correct	110 ms	7716 KB	Output is correct
4	Correct	72 ms	7516 KB	Output is correct
5	Correct	92 ms	7744 KB	Output is correct
6	Correct	105 ms	7432 KB	Output is correct
7	Correct	107 ms	9316 KB	Output is correct
8	Correct	110 ms	7680 KB	Output is correct
9	Correct	106 ms	7428 KB	Output is correct
10	Correct	113 ms	7576 KB	Output is correct
11	Correct	103 ms	7456 KB	Output is correct
12	Correct	104 ms	7624 KB	Output is correct
13	Correct	102 ms	7612 KB	Output is correct
14	Correct	104 ms	7516 KB	Output is correct
15	Correct	90 ms	7512 KB	Output is correct
16	Correct	103 ms	7504 KB	Output is correct
17	Correct	106 ms	7612 KB	Output is correct
18	Correct	71 ms	7592 KB	Output is correct
19	Correct	69 ms	7400 KB	Output is correct
20	Correct	86 ms	7648 KB	Output is correct
21	Correct	132 ms	7516 KB	Output is correct
22	Correct	135 ms	7640 KB	Output is correct
23	Correct	126 ms	7504 KB	Output is correct
24	Correct	130 ms	7412 KB	Output is correct
25	Correct	132 ms	7460 KB	Output is correct
26	Correct	139 ms	7756 KB	Output is correct
27	Correct	133 ms	7540 KB	Output is correct
28	Correct	93 ms	7444 KB	Output is correct
29	Correct	132 ms	7556 KB	Output is correct
30	Correct	141 ms	7644 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	344 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	0 ms	348 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	1 ms	348 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	1 ms	348 KB	Output is correct
52	Correct	1 ms	348 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Correct	1 ms	348 KB	Output is correct
55	Correct	1 ms	348 KB	Output is correct
56	Correct	1 ms	348 KB	Output is correct
57	Correct	1 ms	348 KB	Output is correct
58	Correct	1 ms	348 KB	Output is correct
59	Correct	1 ms	348 KB	Output is correct
60	Correct	1 ms	344 KB	Output is correct
61	Correct	164 ms	7452 KB	Output is correct
62	Correct	160 ms	9552 KB	Output is correct
63	Correct	145 ms	7364 KB	Output is correct
64	Correct	165 ms	7512 KB	Output is correct
65	Correct	151 ms	7528 KB	Output is correct
66	Correct	129 ms	7456 KB	Output is correct
67	Correct	162 ms	7412 KB	Output is correct
68	Correct	117 ms	7588 KB	Output is correct
69	Correct	130 ms	7404 KB	Output is correct
70	Correct	94 ms	7356 KB	Output is correct

답안 #892794

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 8.0 / 8.0

Subtask #3 18.0 / 18.0

Subtask #4 10.0 / 10.0

Subtask #5 11.0 / 11.0

Subtask #6 20.0 / 20.0

Subtask #7 29.0 / 29.0

Subtask #1
4.0 / 4.0

Subtask #2
8.0 / 8.0

Subtask #3
18.0 / 18.0

Subtask #4
10.0 / 10.0

Subtask #5
11.0 / 11.0

Subtask #6
20.0 / 20.0

Subtask #7
29.0 / 29.0