Submission #836650

#	Time	Username	Problem	Language	Result	Execution time	Memory
836650		billyisme	Feast (NOI19_feast)	C++14	100 / 100	103 ms	12784 KiB

feast

/***************************************************************
*             Author : Nguyen Trong Van Viet                   *
*                        Age : 17                              *
*      School : 12T2 Le Khiet High School for the Gifted       *
*            Hometown :  Quang Ngai , Viet Nam .               *
* Khanh An is my lover :) the more I code  , the nearer I am   *
****************************************************************/
#define TASK "text"
#define INPUT TASK".INP" 
#define OUTPUT TASK".OUT"

bool mtt = 0 ;
int test = 1 ;  

#include<bits/stdc++.h>
using namespace std; 

#define int long long 
#define             ll  long long 
#define             db  double 
#define             ve  vector 
#define             vi  vector<int>
#define            vll  vector<ll>
#define            str  string
#define             pb  push_back
#define             pk  pop_back
#define             el  '\n'
#define            pii  pair<int,int>
#define            pll  pair<ll,ll>
#define             mp  make_pair 
#define             fi  first 
#define             se  second
#define         uni(a)  sort(all(a)),a.resize(unique(all(a))-a.begin()) 
#define     FOR(i,a,b)  for(int i=(int)(a);i<=(int)(b);i++)
#define    FORD(i,a,b)  for(int i=(int)(a);i>=(int)(b);i--)
#define    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
#define         all(a)  a.begin(),a.end()  
#define           btpc  __builtin_popcountll
#define             LB  lower_bound
#define             UB  upper_bound 
#define            tct  template<class T>
#define     BIT(msk,i)  (msk>>(i)&1)

ll lg(ll a){return __lg(a);}
ll sq(ll a){return a*a;}  
ll gcd(ll a,ll b){return __gcd(a,b);} 
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll rd(ll l , ll r ){return l+1LL*rand()*rand()*rand()%(r-l+1);}
#define prt(a,n) FOR(i,1,n)cout<<a[i]<<" ";cout<<el;
#define prv(a) for(auto v:a)cout<<v<<" "; cout<<el; 

tct bool mini(T& a,T b){return (a>b)?a=b,1:0;}
tct bool maxi(T& a,T b){return (a<b)?a=b,1:0;}

int xx[] = {0,0,-1,0,1}; 
int yy[] = {0,-1,0,1,0};

const db PI = acos(-1) , EPS = 1e-9;
const ll inf = 1e18 , cs = 331 , sm = 1e9+7; 
const int N = 3e5+5 , oo = 2e9 , LO = 17 , CH = 26 ; 

int n , k; 
int a[N] ; 
ll s[N] ; 
void doc()
{
    cin>> n >> k; 
    FOR(i,1,n)cin>>a[i] , s[i]=s[i-1]+a[i] ; 
}

namespace sub1
{
	pll f[N] ;
	pll CK(ll x)
	{
		f[0] = {0,0};
    // f[i] = s[i]+(f[j]-s[j]+x);
	    pii curmx = {x,-1};
	    FOR(i,1,n+1){
	        f[i] = max(f[i-1],mp(curmx.fi+s[i],curmx.se));
	        maxi(curmx,mp(f[i].fi-s[i]+x,f[i].se-1));
	        // trace(i,f[i].fi,f[i].se);
	    }
	    // return -f[n].se<=k ;
	    return mp(f[n].fi,-f[n].se);
	}
    void xuly()
    {
    	ll l = -1e12 ; 
    	ll r=  1e12 ;
    	ll ans = 0 ; 
    	while(l<=r)
    	{
    		ll mid =(l+r)/2 ; 
    		pll x= CK(mid);
    		if(x.se<=k)
    		{
    			maxi(ans,-mid*x.se+x.fi) ;
    			l=mid+1 ;
    		} 
    		else r=mid-1 ;
    	}
    	cout<<ans;
    }
}

/*  DON'T BELIEVE LOVE WILL INSPIRE YOU ->  TRAIN HARDER ->  YOU WILL GET THE LOVE YOU WANT !!*/

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
    if(fopen(INPUT,"r"))
    {
        freopen(INPUT ,"r",stdin);
        freopen(OUTPUT,"w",stdout);
    }
    if(mtt)cin>>test;

    FOR(i,1,test)
    {
        doc() ; 
        sub1::xuly() ; 
    }
    cerr<<el<<"Love KA : " << clock() <<"ms"<<el;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(INPUT ,"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
feast.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(OUTPUT,"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