oj.uz

Submission #843601

# Submission time Handle Problem Language Result Execution time Memory
843601 2023-09-04T08:19:58 Z fanwen Feast (NOI19_feast) C++17
4 / 100
 82 ms 6484 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 >> 1LL;
    	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 >> 1LL;
      |                 ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5976 KB Output is correct
2 Correct 51 ms 6236 KB Output is correct
3 Correct 52 ms 6228 KB Output is correct
4 Correct 54 ms 6236 KB Output is correct
5 Correct 51 ms 6236 KB Output is correct
6 Correct 62 ms 5980 KB Output is correct
7 Correct 50 ms 5980 KB Output is correct
8 Correct 54 ms 6232 KB Output is correct
9 Correct 54 ms 6208 KB Output is correct
10 Correct 56 ms 6484 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6232 KB Output is correct
2 Correct 51 ms 6236 KB Output is correct
3 Correct 48 ms 6236 KB Output is correct
4 Correct 49 ms 6236 KB Output is correct
5 Incorrect 51 ms 6096 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 6264 KB Output is correct
2 Incorrect 82 ms 6336 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 2392 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 2392 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 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5976 KB Output is correct
2 Correct 51 ms 6236 KB Output is correct
3 Correct 52 ms 6228 KB Output is correct
4 Correct 54 ms 6236 KB Output is correct
5 Correct 51 ms 6236 KB Output is correct
6 Correct 62 ms 5980 KB Output is correct
7 Correct 50 ms 5980 KB Output is correct
8 Correct 54 ms 6232 KB Output is correct
9 Correct 54 ms 6208 KB Output is correct
10 Correct 56 ms 6484 KB Output is correct
11 Correct 51 ms 6232 KB Output is correct
12 Correct 51 ms 6236 KB Output is correct
13 Correct 48 ms 6236 KB Output is correct
14 Correct 49 ms 6236 KB Output is correct
15 Incorrect 51 ms 6096 KB Output isn't correct
16 Halted 0 ms 0 KB -