Submission #13457

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
13457	2015-02-21 03:45:45	ainta	Split the sequence (APIO14_sequence)	C++98	100 / 100	1823 ms	89064 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>
int n, k, w[101000], top;
int Path[210][101000];
long long S[101000], D[2][101000];
struct Stack{
  long long a, b;
  int pv;
}st[101000];
void Add(long long a, long long b, int pv){
  while (top > 1 && (double)(st[top - 1].b - b) / (a - st[top - 1].a) <= (double)(st[top - 1].b - st[top].b) / (st[top].a - st[top - 1].a))top--;
  if (top && st[top].a == a){
    if (st[top].b < b)st[top].b = b;
    return;
  }
  top++;
  st[top].a = a, st[top].b = b, st[top].pv = pv;
}
long long Gap(int t, long long x){
  return st[t].a*x + st[t].b;
}
long long Do(long long x){
  int be = 1, ed = top - 1, mid, r = top;
  while (be <= ed){
    mid = (be + ed) >> 1;
    if (Gap(mid, x) >= Gap(mid + 1, x)){
      r = mid;
      ed = mid - 1;
    }
    else{
      be = mid + 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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