Submission #555344

#	Time	Username	Problem	Language	Result	Execution time	Memory
555344		tht2005	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	26 ms	2504 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct pt {
    int x, y;
    pt(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
};

bool ccw(const pt& a, const pt& b, const pt& c) {
    return (LL)(b.x - a.x) * (c.y - b.y) - (LL)(c.x - b.x) * (b.y - a.y) > 0;
}

const int N = 100005;
int n, m, n1, n2, a;
double x[N], y[N];
LL res;
pt l1[N], l2[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a);
        pt nw(i, a);
        while(n1 > 1 && !ccw(l1[n1 - 2], l1[n1 - 1], nw)) --n1;
        l1[n1++] = nw;
    }
    for(int i = 0; i < m; ++i) {
        scanf("%d", &a);
        pt nw(i, a);
        while(n2 > 1 && !ccw(l2[n2 - 2], l2[n2 - 1], nw)) --n2;
        l2[n2++] = nw;
    }
    x[0] = -1e18;
    for(int i = 1; i < n1; ++i) {
        x[i] = (double)(l1[i].y - l1[i - 1].y) / (l1[i].x - l1[i - 1].x);
    }
    y[0] = -1e18;
    for(int i = 1; i < n2; ++i) {
        y[i] = (double)(l2[i].y - l2[i - 1].y) / (l2[i].x - l2[i - 1].x);
    }
    for(int i = n1 - 1, j = n2 - 1; i || j; ) {
        if(x[i] > y[j]) {
            res += (LL)l2[j].y * (l1[i].x - l1[i - 1].x);
            --i;
        }
        else {
            res += (LL)l1[i].y * (l2[j].x - l2[j - 1].x);
            --j;
        }
    }
    printf("%lld", res);
    return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
kyoto.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60