Submission #523086

#	Time	Username	Problem	Language	Result	Execution time	Memory
523086		lobo_prix	Feast (NOI19_feast)	C++17	100 / 100	415 ms	14012 KiB

feast

//[Author]   tuxedcat
//[Date]     2022.02.07
//[File]     src/feast.cpp
//[Library]  https://github.com/tuxedcat/pslib
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
using namespace std;

// #define int i64
#define FP_EPS 1e-1
#define COUT_FP 11
using f64=long double; //long double(살짝느림),__float128(매우느림)
//#define CPP20 1
#define DBG_SETW 3
#define endl '\n' //remove it when interactive

#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define itos to_string
#define head(x) (x.begin())
#define tail(x) prev(x.end())
#define dbg(...) void(0)
#define dbgif(...) void(0)
#define dbg1(...) void(0)
#define dbg1if(...) void(0)
using i64=long long;using u64=unsigned long long;using u32=unsigned;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=greater<>>using PQ=std::priority_queue<T,vector<T>,CMP>;
//functions before include <arr.h>

//Math
#if !(CPP20)
	#define countl_zero(x) __builtin_clzll(x)
	#define popcount(x) __builtin_popcountll(x)
	#define bit_ceil(x) 1<<clg2(x)
#endif
template<class T>int sz(const T& x){return x.size();}
int fdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
int cdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
i64 flg2(u64 x){return 63-countl_zero(x);}
i64 clg2(u64 x){return 64-countl_zero(x-1);}
int fsqrt(i64 n) {i64 i=1;while(i*i<=n)i++;return i-1;}
int csqrt(i64 n) {i64 i=1;while(i*i<n)i++;return i;}
template<class T>T sq(T x){return x*x;}
template<class T>constexpr T inf(){return numeric_limits<T>::max()/2;}
template<class T>constexpr T nan(){return inf<T>()+1;}
#ifdef CPP20
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<typename T> concept MemberNan=requires(T t){t.nan();};
template<MemberInf T>T inf(){return T().inf();}
template<MemberNan T>T nan(){return T().nan();}
#endif

//IO & misc
template<class...A>void print(A...a){((cout<<a),...);}
template<class...A>void println(A...a){((cout<<a),...,(cout<<endl));}
template<class T=int>T input(){T x;cin>>x;return x;}
template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
void MUST(bool expr){
#if DEBUG
	#include <csignal>
	if(!expr)
		raise(SIGINT);
#endif
}
#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}

template<class T, class P=vector<T>>
struct Arr:public P{
	Arr(){P::shrink_to_fit();}
	explicit Arr(signed n):P(n){}
	explicit Arr(signed n,T init):P(n,init){}
	Arr(initializer_list<T>il):P(il){}
	Arr(auto its, auto ite):P(its,ite){}
	inline T& operator[](signed i){
		int n=sz(*this);
		if(i<0)i+=n,dbg1("Neg Index Found");
		if(i>=n)i-=n,dbg1("Over Index Found");
		return P::operator[](i);
	}
	const T& operator[](signed i)const{	
		int n=sz(*this);
		if(i<0)i+=n,dbg1("Neg Index Found");
		if(i>=n)i-=n,dbg1("Over Index Found");
		return P::operator[](i);
	}
	T& at(signed i){return *this[i];}
	const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}

//Consts
// const f64 pi=numbers::pi_v<f64>,eps=FP_EPS;
const f64 pi=acos(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//functions after include <arr.h>

template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
Arr<int> permuinv(const Arr<int>& a){Arr<int> r(sz(a));for(int i=0;i<sz(a);i++)r[a[i]]=i;return r;}
template<class T>map<T,Arr<int>> classify(const Arr<T>& a){
	map<T,Arr<int>> r;
	for(int i=0;i<sz(a);i++)
		r[a[i]].push_back(i);
	return r;
}

//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//

const int N=300001;
int n,k;
int a[N];
i64 dp[N][2],dpinit[N][2];
i64 f(i64 x){
	memcpy(dp,dpinit,sizeof dp);
	dp[0][0]=0;
	dp[0][1]=a[0]-x;
	for(int i=1;i<n;i++){
		assmax(dp[i][0],max(dp[i-1][0],dp[i-1][1]));
		assmax(dp[i][1],max(dp[i-1][0]+a[i]-x,dp[i-1][1]+a[i]));
	}
	return max({0ll,dp[n-1][0],dp[n-1][1]})+x*k;
}

void solve(){
	for(int i=0;i<N;i++)
		dpinit[i][0]=dpinit[i][1]=-inf<i64>();
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	i64 s=0,e=inf<i64>()/k;
	while(e-s>2){
		i64 m1=(s*2+e)/3,m2=(s+e*2)/3;
		if(f(m1)>f(m2)) s=m1;
		else e=m2;
	}
	println(min({f(s),f(s+1),f(e)}));
}
signed main(){
	// int ti=0,t;cin>>t;
	// while(++ti<=t)
	// 	cout<<"Case #"<<ti<<": ",
		solve();
}

Compilation message (stderr)

feast.cpp:87:6: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   87 |  Arr(auto its, auto ite):P(its,ite){}
      |      ^~~~
feast.cpp:87:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   87 |  Arr(auto its, auto ite):P(its,ite){}
      |                ^~~~
feast.cpp:103:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  103 | template<class... A> auto ARR(auto n,A&&... a)
      |                               ^~~~

• 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