Submission #856414

#	Time	Username	Problem	Language	Result	Execution time	Memory
856414		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	187 ms	12580 KiB

feast

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <array>
#include <numeric>
#include <queue>
#include <deque>
#include <cmath>
#include <climits>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;


const int MOD = 998244353;
const long double PI = 3.141592653589793;
using ll = long long;
const ll INF = 1e18;

#define int ll

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

// template<typename K, typename V>
// using hash_table = cc_hash_table<K, V, hash<K>>;

template<typename T>
using graph = vector<vector<T>>;

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for (auto& i: a) {
        in >> i;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& a) {
    for (auto& i: a) {
        out << i << " ";
    }
    return out;
}

ll fast_pow(ll a, ll b, ll mod) {
    if (b == 0)
        return 1;
    if (b % 2) {
        return (1ll * a * fast_pow(a, b - 1, mod)) % mod;
    }
    ll k = fast_pow(a, b / 2, mod);
    return (1ll * k * k) % mod;
}

ll fast_pow(ll a, ll b) {
    if (b == 0)
        return 1;
    if (b % 2) {
        return (1ll * a * fast_pow(a, b - 1));
    }
    ll k = fast_pow(a, b / 2);
    return (1ll * k * k);
}
int n, k;
vector<int> a;

pair<int, int> calc(int L) {
	vector<int> dp(n), c(n);
	int cnt = 0;
	int mx = 0;
	int mx_dp = 0;
	int cnt_dp = 0;

	for (int i = 0; i < n; i++) {
		dp[i] = a[i] - L + mx;
		c[i] = cnt + 1;
		if (mx_dp > dp[i]) {
			dp[i] = mx_dp;
			c[i] = cnt_dp;
		}

		if (dp[i] > mx_dp) {
			mx_dp = dp[i];
			cnt_dp = c[i];
		}

		if (mx <= -a[i] + mx_dp) {
			mx = -a[i] + mx_dp;
			cnt = cnt_dp;
		}
	}
	return {dp.back(), c.back()};
}

void solve() {
	cin >> n >> k;
	a.resize(n);
	cin >> a;
	int cnt = 0, sum = 0;
	bool f = 0;
	for (int i : a) {
		if (i > 0) {
			f = 1;
			sum += i;
		} else if (i < 0) {
			cnt += f;
			f = 0;
		}
	}
	cnt += f;
	if (cnt <= k) {
		cout << sum << "\n";
		return;
	}

	for (int i = 1; i < n; i++)
		a[i] += a[i - 1];

	int l = 0;
	int r = INF;
	while (r - l > 1) {
		int mid = (r + l) / 2;
		if (calc(mid).second > k) {
			l = mid;
		} else {
			r = mid;
		}
	}
	// cerr << calc(0).second <<" " << calc(0).first << endl;
	// return;
	// cerr << r << " " << calc(r).second << endl;
	cout << calc(r).first + k * r;

	// for (int L = -5; L <= 15; L++) {
	// 	cerr << calc(L).second << " ";
	// }
}

int32_t main(int32_t argc, const char * argv[]) {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
    // insert code here...
    int tt= 1;
    // std::cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29