Submission #1103147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103147		DuongKiet	Feast (NOI19_feast)	C++17	100 / 100	101 ms	12360 KiB

feast

#include <bits/stdc++.h>
#define N 300005
#define inf (long long) 1e17
#define ll long long
#define int long long
#define ii pair <int,long long>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back

using namespace std;

const unsigned ll Mod = 1000000007LL;

int n, k, a[N];
void init(){

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}
bool ifsub1(){

    for (int i = 1; i <= n; i++)
        if (a[i] < 0) return 0;
    return 1;
}
void sub1(){

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i];
    cout << ans << '\n';
}
int pos;
bool ifsub2(){

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] < 0) {pos = a[i]; cnt++;}
    return (cnt < 2);
}
void sub2(){

    int sum = 0, suml = 0, am = 0;
    bool kt = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < 0) {
            kt = 1;
            am = a[i];
        }
        if (!kt) suml += a[i];
        sum += a[i];
    }
    if (k > 1)
        cout << sum - am << '\n';
    else cout << max(suml, max(sum, sum - suml - am));
}
void sub3(){
    int ans = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(0ll, res + a[i]);
        ans = max(ans, res);
    }
    cout << ans << '\n';
}
//int pa[N], sz[N];
//int findpa(int u){
//
//    if (u == pa[u]) return u;
//    return pa[u] = findpa(pa[u]);
//}
//void Union(int a, int b){
//
//    a = findpa(a);
//    b = findpa(b);
//    if (a == b) return;
//    if (sz[a] < sz[b]) swap(a,b);
//    pa[b] = a;
//    sz[a] += sz[b];
//    sum[a] += sum[b];
//}
//vector <ii> d;
//void Add(int u){
//    d.pb({u, sum[u]});
//}
//void sub6(){
//    for (int i = 1; i <= n; i++){
//        pa[i] = i;
//        sz[i] = 1;
//        sum[i] = a[i];
//    }
//    int parduong, param;
//    bool task = 0;
//    if (a[1] >= 0) {parduong = 1; task = 1;}
//    else param = 1;
//    for (int i = 1; i <= n; i++){
//        if (a[i] >= 0) {
//            if (task)
//                Union(parduong, i);
//            else parduong = i;
//            task = 1;
//        }
//        else {
//            if (!task) Union(param, i);
//            else param = i;
//            task = 0;
//        }
//    }
//    int curpa = findpa(1);
//    Add(curpa);
//    for (int i = 1; i <= n; i++){
//        int u = findpa(i);
//        if (u != curpa){
//            curpa = u;
//            Add(u);
//        }
//    }
//    for (int i = 2; i < d.size(); i++){
//        if (d[i].se > 0 && d[i-2].se > 0){
//            g.pb({d[i].fi, d[i - 2].fi, d[i].se + d[i].se });
//        }
//    }
//}
pair<int, int> dp[N + 1][2];

bool check(int res) {
	dp[0][0] = {0, 0}, dp[0][1] = {-inf, 0};
	for (int i = 1; i <= n; ++i) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		dp[i][1] =
		    max(make_pair(dp[i - 1][1].fi + a[i], dp[i - 1][1].se),
		        make_pair(dp[i - 1][0].fi + a[i] - res, dp[i - 1][0].se + 1));
	}
	return max(dp[n][0], dp[n][1]).se >= k;
};
void solve(){

    int l = 0, r = 1e14;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	int res = l;
	check(res);
	cout << res * k + max(dp[n][0].fi, dp[n][1].fi);
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    #define nametask "PRESUFF"
    if(fopen(nametask".inp", "r")) {
        freopen(nametask".inp", "r", stdin);
        freopen(nametask".out", "w", stdout);
    }
    init();
//    if (ifsub1()) return sub1(), 0;
//    if (ifsub2()) return sub2(), 0;
//    if (k == 1) return sub3(), 0;
//    if (k <= n && n <= 2000) return sub6(), 0;
    solve();
    return 0;
}
/// Duong Anh Kiet from Kien Giang ///
/*
6 1
-1 -2 -1 2 -1 2
*/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(nametask".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(nametask".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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