Submission #319742

#	Time	Username	Problem	Language	Result	Execution time	Memory
319742		soroush	Feast (NOI19_feast)	C++14	71 / 100	441 ms	8164 KiB

feast

//*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 3e5+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);

#define int ll
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , k;
ll dp[maxn];
ll sum[maxn];
int a[maxn];

struct segment{
	int seg[maxn*4];
	int lazy[maxn*4];
	void build(int v = 1  , int l = 1 , int  r = n + 1){
		if(r - l == 1){
			seg[v] = dp[l] - sum[l];
			return;
		}
		int mid = (l + r) / 2;
		build(2*v , l , mid);
		build(2*v + 1 , mid , r);
		seg[v] = max(seg[2*v] , seg[2*v + 1]);
	}
	void shift(int v , int l , int r){
		seg[v] += lazy[v];
		if(r - l > 1)
			lazy[2*v] += lazy[v] , lazy[2*v + 1] += lazy[v];
		lazy[v] = 0;
	}
	void update(int L , int R , int x, int v = 1 , int l = 1 , int r = n + 1){
		shift(v , l , r);
		if(r <= L or R <= l)
			return;
		if(L <= l and r <= R){
			lazy[v] += x;
			shift(v , l , r);
			return;
		}
		int mid = (l + r) / 2;
		update(L , R  , x , 2*v , l , mid);
		update(L , R , x , 2*v + 1 , mid , r);
		seg[v] = max(seg[2*v] , seg[2*v + 1]);
	}
	int query(int L , int R , int v = 1 , int l = 1 , int r = n + 1){
		shift(v , l , r);
		if(r <= L or R <= l)
			return(0);
		if(L <= l and r <= R)
			return(seg[v]);
		int mid = (l + r)/2;
		return(max(query(L , R , 2*v , l , mid) , query(L , R , 2*v + 1, mid , r)));
	}
};

segment seg; //shans 100

void sub1(){ //10 + 11 (+ 20 ?) 
	ll mn = 0;
	for(int i = 1 ; i <= n ; i ++)
		dp[i] = max({dp[i] , dp[i - 1] , sum[i] - mn}) , mn = min(mn , sum[i]);
	for(int j = 2 ; j <= k ; j ++){
		seg.build();
		for(int i = 1 ; i <= n ; i  ++ )
			dp[i] = max(dp[i-1] , sum[i] + seg.query(1 , i));
	}
    dokme(dp[n]);
}

void sub2(){ //18
	ll ans = 0;
	ll mn = 0;
	for(int i = 1 ; i <= n ; i ++)
		ans = max(ans , sum[i] - mn) , mn = min(mn , sum[i]);
	dokme(ans);
}

void sub3(){ //8
	ll ans = 0;
	for(int i = 1 ; i <= n ; i ++)
		ans += max(0LL , a[i]);
	dokme(ans);
}

void sub4(){ //4
	dokme(sum[n]);
}

int32_t main(){
    migmig;
    cin >> n >> k;
    int cnt = 0;
    for(int i = 1 ; i <= n ; i ++)
		cin >> a[i] , cnt+=(a[i] < 0);
	for(int i = 1;  i <= n ; i ++)
		sum[i] = sum[i-1] + a[i];
	if(n <= 2000 and k <= 2000){
		sub1();
	}
	if(*min_element(a+1 , a + n + 1) >= 0)
		sub4();
	if(k == 1){
		sub2();
	}
	if(cnt <= 1){
		sub3();
	}
	dokme("8===o");
    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: 0 / 29