제출 #928597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928597		ind1v	Bigger segments (IZhO19_segments)	C++11	0 / 100	1 ms	2520 KiB

segments

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

struct point_t {
  long long x, y;
  
  point_t() {}
  
  point_t(long long _x, long long _y) : x(_x), y(_y) {}
};

struct vector_t {
  long long x, y;
  
  vector_t() {}
  
  vector_t(point_t a, point_t b) : x(b.x - a.x), y(b.y - a.y) {}
  
  long long cross(vector_t o) {
    return x * o.y - y * o.x;
  }
};

bool cw(point_t a, point_t b, point_t c) {
  vector_t ab(a, b), ac(a, c);
  return ab.cross(ac) < 0;
}

int n;
int a[N];
point_t p[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  long long s = 0;
  p[0] = point_t(0, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s += a[i];
    p[i] = point_t(i, s);
  }
  vector<point_t> v;
  v.push_back(p[0]);
  v.push_back(p[1]);
  for (int i = 2; i <= n; i++) {
    while ((int) v.size() >= 2 && cw(v[(int) v.size() - 2], v.back(), p[i])) {
      v.pop_back();
    }
    v.push_back(p[i]);
  }
  cout << (int) v.size() - 1 << '\n';
  return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27