Submission #791657

#	Time	Username	Problem	Language	Result	Execution time	Memory
791657		vjudge1	Feast (NOI19_feast)	C++17	12 / 100	141 ms	20676 KiB

feast

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
//#define ld long double
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
const int inf = 1e18;
const int MN = 1e6+5;
const int mod = 1e9+7;
const int base=317;
int pre[MN],a[MN];
int n,k;
pii dp[MN];
bool Aliens_trick(int x) {
	memset(dp,0,sizeof(dp));
	pii mx={0,0};
	for (int i=1; i<=n; i++) {
		pii cur={dp[i].fi-pre[i], dp[i].se};
		if(cur.fi>mx.fi||cur.fi==mx.fi&&cur.se<mx.se) {
			mx=cur;
		}
		pii res={mx.fi-x+pre[i+1], mx.se+1};
		dp[i+1]=dp[i];
		if(res.fi>dp[i+1].fi||res.fi==dp[i+1].fi&&res.se<dp[i+1].se) {
			dp[i+1]=res;
		}
	}
	if (dp[n+1].se<=k) return true;
	else return false;
}
inline void solve() {
	cin>>n>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	int l=0, r=3e14;
	while(l<r) {
		int m=(l+r)/2;
		if(Aliens_trick(m)) r=m;
		else l=m+1;
	}
	Aliens_trick(l);
	cout<<dp[n+1].fi+l*k;
}	
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
//	preprocess();
//	cin>>t;
	while(t--) {
		solve();
	}
		
}

Compilation message (stderr)

feast.cpp: In function 'bool Aliens_trick(long long int)':
feast.cpp:21:24: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   21 |  memset(dp,0,sizeof(dp));
      |                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from feast.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
feast.cpp:25:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |   if(cur.fi>mx.fi||cur.fi==mx.fi&&cur.se<mx.se) {
      |                                 ^
feast.cpp:30:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |   if(res.fi>dp[i+1].fi||res.fi==dp[i+1].fi&&res.se<dp[i+1].se) {
      |                                           ^

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