oj.uz

Submission #836648

# Submission time Handle Problem Language Result Execution time Memory
836648 2023-08-24T13:40:56 Z billyisme Feast (NOI19_feast) C++14
30 / 100
 83 ms 12740 KB 
/***************************************************************
*             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);
	    pll 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)
    		{
    			ans=mid ; 
    			l=mid+1 ;
    		} 
    		else r=mid-1 ;
    	}
    	CK(ans) ;
    	cout<<f[n].fi+f[n].se*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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12156 KB Output is correct
2 Correct 57 ms 12376 KB Output is correct
3 Correct 59 ms 12492 KB Output is correct
4 Correct 64 ms 12488 KB Output is correct
5 Correct 56 ms 12424 KB Output is correct
6 Correct 55 ms 12112 KB Output is correct
7 Correct 63 ms 12220 KB Output is correct
8 Correct 56 ms 12456 KB Output is correct
9 Correct 54 ms 12244 KB Output is correct
10 Correct 55 ms 12372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10584 KB Output is correct
2 Correct 48 ms 10836 KB Output is correct
3 Correct 45 ms 10572 KB Output is correct
4 Correct 47 ms 10672 KB Output is correct
5 Correct 47 ms 12108 KB Output is correct
6 Correct 52 ms 10456 KB Output is correct
7 Correct 48 ms 10792 KB Output is correct
8 Correct 53 ms 12676 KB Output is correct
9 Correct 48 ms 12108 KB Output is correct
10 Correct 47 ms 10708 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12616 KB Output is correct
2 Correct 71 ms 12464 KB Output is correct
3 Correct 67 ms 12580 KB Output is correct
4 Correct 75 ms 12368 KB Output is correct
5 Correct 68 ms 12492 KB Output is correct
6 Correct 71 ms 12620 KB Output is correct
7 Correct 69 ms 12704 KB Output is correct
8 Correct 68 ms 12492 KB Output is correct
9 Correct 69 ms 12740 KB Output is correct
10 Correct 69 ms 12700 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12156 KB Output is correct
2 Correct 57 ms 12376 KB Output is correct
3 Correct 59 ms 12492 KB Output is correct
4 Correct 64 ms 12488 KB Output is correct
5 Correct 56 ms 12424 KB Output is correct
6 Correct 55 ms 12112 KB Output is correct
7 Correct 63 ms 12220 KB Output is correct
8 Correct 56 ms 12456 KB Output is correct
9 Correct 54 ms 12244 KB Output is correct
10 Correct 55 ms 12372 KB Output is correct
11 Correct 47 ms 10584 KB Output is correct
12 Correct 48 ms 10836 KB Output is correct
13 Correct 45 ms 10572 KB Output is correct
14 Correct 47 ms 10672 KB Output is correct
15 Correct 47 ms 12108 KB Output is correct
16 Correct 52 ms 10456 KB Output is correct
17 Correct 48 ms 10792 KB Output is correct
18 Correct 53 ms 12676 KB Output is correct
19 Correct 48 ms 12108 KB Output is correct
20 Correct 47 ms 10708 KB Output is correct
21 Correct 83 ms 12616 KB Output is correct
22 Correct 71 ms 12464 KB Output is correct
23 Correct 67 ms 12580 KB Output is correct
24 Correct 75 ms 12368 KB Output is correct
25 Correct 68 ms 12492 KB Output is correct
26 Correct 71 ms 12620 KB Output is correct
27 Correct 69 ms 12704 KB Output is correct
28 Correct 68 ms 12492 KB Output is correct
29 Correct 69 ms 12740 KB Output is correct
30 Correct 69 ms 12700 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Incorrect 1 ms 340 KB Output isn't correct
33 Halted 0 ms 0 KB -