Submission #15773

#	Time	Username	Problem	Language	Result	Execution time	Memory
15773		comet	달리는 게임 (kriii3_E)	C++98	Compilation error	0 ms	0 KiB

E

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
ll s[1000010],d[1000010],p[1000010],p2[1000010];
vector<ll> a,b;
void push(ll n,ll m){
	int sz=a.size();
	while(  sz>1  &&  (b[sz-1]-b[sz-2])*(a[sz-1]-n)  >=  (m-b[sz-1])*(a[sz-2]-a[sz-1])  ){
		sz--;
		a.pop_back();
		b.pop_back();
	}
	a.push_back(n);
	b.push_back(m);
}
ll query(ll x){
	if(a.size()==1)return a[0]*x+b[0];
	int lo=0,hi=a.size(),mid;
	while(lo+1<hi){
		mid=(lo+hi)/2;
		if(b[mid]-b[mid-1]<x*(a[mid-1]-a[mid])){
			hi=mid;
		}
		else{
			lo=mid;
		}
	}
	return a[lo]*x+b[lo];
}
int main(){
	ll n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		p[i]=p[i-1]+s[i];
		p2[i]=p2[i-1]+i*s[i];
	}
	push(-1,-p2[1]+p[1]);
	for(ll i=1;i<=n;i++){
		d[i]=p2[i];
		/*for(ll j=0;j<i;j++){
			d[i]=max(d[i],  -(j+1)*p[i]  +d[j]-p2[j+1]+(j+1)*p[j+1]  +p2[i]  );
		}*/
		d[i]=max(d[i],query(p[i])+p2[i]);
		push(-(i+1),d[i]-p2[i+1]+(i+1)*p[i+1]);
	}
	cout<<d[n];
}

Compilation message (stderr)

E.cpp:7:1: error: ‘vector’ does not name a type
 vector<ll> a,b;
 ^
E.cpp: In function ‘void push(ll, ll)’:
E.cpp:9:9: error: ‘a’ was not declared in this scope
  int sz=a.size();
         ^
E.cpp:10:21: error: ‘b’ was not declared in this scope
  while(  sz>1  &&  (b[sz-1]-b[sz-2])*(a[sz-1]-n)  >=  (m-b[sz-1])*(a[sz-2]-a[sz-1])  ){
                     ^
E.cpp:16:2: error: ‘b’ was not declared in this scope
  b.push_back(m);
  ^
E.cpp: In function ‘ll query(ll)’:
E.cpp:19:5: error: ‘a’ was not declared in this scope
  if(a.size()==1)return a[0]*x+b[0];
     ^
E.cpp:19:31: error: ‘b’ was not declared in this scope
  if(a.size()==1)return a[0]*x+b[0];
                               ^
E.cpp:20:14: error: ‘a’ was not declared in this scope
  int lo=0,hi=a.size(),mid;
              ^
E.cpp:22:3: error: ‘mid’ was not declared in this scope
   mid=(lo+hi)/2;
   ^
E.cpp:23:6: error: ‘b’ was not declared in this scope
   if(b[mid]-b[mid-1]<x*(a[mid-1]-a[mid])){
      ^
E.cpp:30:17: error: ‘b’ was not declared in this scope
  return a[lo]*x+b[lo];
                 ^
E.cpp: In function ‘int main()’:
E.cpp:33:7: warning: unused variable ‘ans’ [-Wunused-variable]
  ll n,ans=0;
       ^
E.cpp: In function ‘ll query(ll)’:
E.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^