Submission #110854

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
110854	2019-05-12 15:13:16	evpipis	Split the sequence (APIO14_sequence)	C++17	0 / 100	127 ms	84040 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;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int len = 1e5+5;
int arr[len], pos, pref[len], po[len][205];
ll dp[len];
vector<pll> vec;
ll func(pll line, ll x){
    return line.fi*x+line.se;
}
bool can(pll a, pll b, pll c){
    return (double)(a.se-b.se)/(double)(b.fi-a.fi) >= (double)(b.se-c.se)/(double)(c.fi-b.fi);
}
void add(pll cur){
    while (vec.size() >= 2 && can(vec[vec.size()-2], vec.back(), cur))
        vec.pop_back();
    vec.pb(cur);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> query(ll)':
sequence.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= vec.size())
         ~~~~^~~~~~~~~~~~~
sequence.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pos+1 < vec.size() && func(vec[pos+1], x) > func(vec[pos], x))
            ~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k), k++;
     ~~~~~~~~~~~~~~~~~~~~~~^~~~~
sequence.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

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