답안 #15776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15776 2015-07-22T11:17:18 Z comet 달리는 게임 (kriii3_E) C++
70 / 70
514 ms 33104 KB
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
ll s[1000010],d[1000010],p[1000010],p2[1000010];
deque<ll> a,b,c;
int cnt=0;
void push(ll n,ll m){
	int sz=a.size();
	while(  sz>1  &&  (b[0]-b[1])*(a[0]-n)  < (m-b[0])*(a[1]-a[0])  ){
		sz--;
		a.pop_front();
		b.pop_front();
		c.pop_front();
	}
	a.push_front(n);
	b.push_front(m);
	c.push_front(cnt++);
}
ll query(ll x,ll y){
	if(a.size()==1)return a[0]*x+b[0]+y;
	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]+y;
}
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];
		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];
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 32976 KB Output is correct
2 Correct 0 ms 32976 KB Output is correct
3 Correct 0 ms 32976 KB Output is correct
4 Correct 0 ms 32976 KB Output is correct
5 Correct 0 ms 32976 KB Output is correct
6 Correct 0 ms 32976 KB Output is correct
7 Correct 0 ms 32976 KB Output is correct
8 Correct 0 ms 32976 KB Output is correct
9 Correct 0 ms 32976 KB Output is correct
10 Correct 0 ms 32976 KB Output is correct
11 Correct 0 ms 32976 KB Output is correct
12 Correct 0 ms 32976 KB Output is correct
13 Correct 0 ms 32976 KB Output is correct
14 Correct 0 ms 32976 KB Output is correct
15 Correct 0 ms 32976 KB Output is correct
16 Correct 2 ms 32976 KB Output is correct
17 Correct 0 ms 32976 KB Output is correct
18 Correct 0 ms 32976 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 32976 KB Output is correct
2 Correct 29 ms 32976 KB Output is correct
3 Correct 28 ms 32976 KB Output is correct
4 Correct 59 ms 32976 KB Output is correct
5 Correct 53 ms 33104 KB Output is correct
6 Correct 58 ms 32976 KB Output is correct
7 Correct 263 ms 32976 KB Output is correct
8 Correct 513 ms 32976 KB Output is correct
9 Correct 514 ms 32976 KB Output is correct