Submission #20820

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
20820	2017-02-17 12:34:55	kdh9949	Split the sequence (APIO14_sequence)	C++14	100 / 100	613 ms	88748 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
struct Cht{
  struct Line{
    ll a, b; int x;
  };
    double cr(Line p, Line q){
        return (q.b - p.b) * 1.0 / (p.a - q.a);
    }
  Line dq[100010];
  int f, r;
  void clr(){ f = r = 0; }
  void upd(ll a, ll b, int x){
    Line cur = {a, b, x};
        while(f + 1 < r && ((dq[r - 1].a == cur.a && dq[r - 1].b <= cur.b) ||
              (dq[r - 1].a != cur.a && cr(dq[r - 2], cur) <= cr(dq[r - 2], dq[r - 1])))) r--;
        if(f == r || dq[r - 1].a != cur.a) dq[r++] = cur;
  }
  pli query(ll x){
    while(f + 1 < r && x >= cr(dq[f], dq[f + 1])) f++;
    return {dq[f].a * x + dq[f].b, dq[f].x};
  }
}C;
int n, k, b[210][100010];
ll s[100010], dp[2][100010];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:38:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:40:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", s + i);
                       ^

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