Submission #20827

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
20827	2017-02-23 01:37:38	kdh9949	Divide and conquer (IZhO14_divide)	C++14	100 / 100	73 ms	4824 KiB

divide

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;
int n, x[100010], sz;
ll g[100010], e[100010], ans;
vector<int> v;
int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf("%d%lld%lld", x + i, g + i, e + i);
    g[i] += g[i - 1];
    e[i] += e[i - 1];
  }
  for(int i = n, s, en; i >= 1; i--){
    while(sz > 1 && 1L * (e[i - 1] - e[v[sz - 1]]) / (x[i] - x[v[sz - 1]]) <
            1L * (e[v[sz - 1]] - e[v[sz - 2]]) / (x[v[sz - 1]] - x[v[sz - 2]])){ v.pop_back(); sz--; }
    v.push_back(i); sz++;
    s = 0; en = sz - 1;
    while(s <= en){
      int m = (s + en) / 2;
      if(e[v[m] - (v[m] == i)] - e[i - 1] >= x[v[m]] - x[i]) en = m - 1;
      else s = m + 1;
    }
    ans = max(ans, g[v[s]] - g[i - 1]);
    v.pop_back(); sz--;
    while(sz > 1 && 1L * (e[i] - e[v[sz - 1]]) / (x[i] - x[v[sz - 1]]) <
            1L * (e[v[sz - 1]] - e[v[sz - 2]]) / (x[v[sz - 1]] - x[v[sz - 2]])){ v.pop_back(); sz--; }
    v.push_back(i); sz++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
divide.cpp:12:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%lld", x + i, g + i, e + i);
                                           ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52