oj.uz

Submission #843599

# Submission time Handle Problem Language Result Execution time Memory
843599 2023-09-04T08:17:01 Z fanwen Feast (NOI19_feast) C++17
4 / 100
 82 ms 9316 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int MAXN = 3e5 + 5;

int N, K, cnt[MAXN];
long long a[MAXN], dp[MAXN];

bool check(long long val) {
	pair <long long, int> best(0, 0);
	FOR(i, 1, N) {
		dp[i] = dp[i - 1], cnt[i] = cnt[i - 1];
		if(maximize(dp[i], best.first + a[i] - val)) {
			cnt[i] = cnt[best.second] + 1;
		}

		if(maximize(best.first, dp[i] - a[i])) {
			best.second = i;
		}
	}
	return cnt[N] <= K;
}

void you_make_it(void) {

    cin >> N >> K;
    FOR(i, 1, N) cin >> a[i], a[i] += a[i - 1];
    long long L = -1, R = 1E18;
    while(R - L > 1) {
    	auto Mid = L + R >> 1;
    	if(check(Mid)) R = Mid;
    	else L = Mid;
    }
    cout << dp[N] + 1LL * cnt[N] * R;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

feast.cpp: In function 'void you_make_it()':
feast.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |      auto Mid = L + R >> 1;
      |                 ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9008 KB Output is correct
2 Correct 57 ms 9316 KB Output is correct
3 Correct 57 ms 9200 KB Output is correct
4 Correct 52 ms 9152 KB Output is correct
5 Correct 57 ms 9120 KB Output is correct
6 Correct 51 ms 9008 KB Output is correct
7 Correct 52 ms 8788 KB Output is correct
8 Correct 52 ms 9044 KB Output is correct
9 Correct 53 ms 8796 KB Output is correct
10 Correct 52 ms 9044 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7344 KB Output is correct
2 Correct 51 ms 7444 KB Output is correct
3 Correct 48 ms 7108 KB Output is correct
4 Correct 48 ms 7344 KB Output is correct
5 Incorrect 52 ms 9012 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9008 KB Output is correct
2 Correct 57 ms 9316 KB Output is correct
3 Correct 57 ms 9200 KB Output is correct
4 Correct 52 ms 9152 KB Output is correct
5 Correct 57 ms 9120 KB Output is correct
6 Correct 51 ms 9008 KB Output is correct
7 Correct 52 ms 8788 KB Output is correct
8 Correct 52 ms 9044 KB Output is correct
9 Correct 53 ms 8796 KB Output is correct
10 Correct 52 ms 9044 KB Output is correct
11 Correct 52 ms 7344 KB Output is correct
12 Correct 51 ms 7444 KB Output is correct
13 Correct 48 ms 7108 KB Output is correct
14 Correct 48 ms 7344 KB Output is correct
15 Incorrect 52 ms 9012 KB Output isn't correct
16 Halted 0 ms 0 KB -