Submission #218398

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
218398	2020-04-02 06:28:14	spdskatr	Split the sequence (APIO14_sequence)	C++14	0 / 100	260 ms	7032 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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef pair<long double, int> line;
typedef __int128_t ll;
int N, K, ar[100005], ps[100005];
int cnt[100005], from[100005];
ll dp[100005], m[100005], c[100005];
vector<int> cht;
void ins(int j) {
  m[j] = ps[j];
  c[j] = dp[j] - ps[j]*ps[N];
  while (cht.size() > 1) {
    int s = cht[cht.size() - 2];
    int t = cht[cht.size() - 1];
    if ((c[s] - c[j])*(m[t] - m[s]) <= (c[s] - c[t])*(m[j] - m[s])) {
      cht.pop_back();
    } else break;
  }
  cht.push_back(j);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'void solve(ll)':
sequence.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr + 1 < cht.size()) {
          ~~~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", ar+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