Submission #5686

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
5686	2014-05-13 01:47:48	cki86201	Split the sequence (APIO14_sequence)	C++98	100 / 100	516 ms	85860 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<set>
typedef long long ll;
typedef std::pair<ll,ll> pl;
#define X first
#define Y second
int n, k, s[100010];
ll d[2][100010];
int b[202][100010];
int ans[202];
struct deq{
  pl p[100010];
  int w[100010];
  int f, r;
  void init(){f=r=0;}
  void push(pl x,int c){
    while(f-r>1 && (p[f-1].X - p[f-2].X) * (x.Y - p[f-1].Y) >= (x.X - p[f-1].X) * (p[f-1].Y - p[f-2].Y))--f;
    p[f] = x, w[f++] = c;
  }
  ll pop(ll x){
    while(f-r>1 && (x*p[r].X + p[r].Y) <= (x*p[r+1].X + p[r+1].Y))++r;
    return x*p[r].X + p[r].Y;
  }
  inline int prev(){return w[r];}
}Deq[2];
int main()
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29