Submission #1302813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302813		baotoan655	Long Distance Coach (JOI17_coach)	C++20	100 / 100	94 ms	12780 KiB

coach

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
#define int long long
const long long INF = 1e18;
const int inf = 2e9;
struct line {
    long long a, b;
    long long val(long long x) {
        return a * x + b;
    }
};
const int N = 200005;
line hull[N];
int pt;
double intersect(line x, line y) {
    return (double) (x.b - y.b) / (y.a - x.a);
}
bool bad(line x, line y, line z) {
    return intersect(x, z) < intersect(x, y);
}
void add(long long a, long long b) {
    hull[++pt] = {a, b};
    while(pt >= 3 && bad(hull[pt - 2], hull[pt - 1], hull[pt])) {
        hull[pt - 1] = hull[pt];
        --pt;
    }
}
long long query(long long x) {
    int l = 1, r = pt, mid, res = pt;
    while(l < r) {
        mid = (l + r) >> 1;
        if(hull[mid].val(x) > hull[mid + 1].val(x)) l = mid + 1;
        else {
            res = mid;
            r = mid;
        }
    }
    return hull[res].val(x);
}
long long X;
int n, m, W, T;
pair<int, int> s[N];
pair<int, int> a[N];
long long dp[N], pref[N];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    file("A") else file("task");
    cin >> X >> n >> m >> W >> T;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i].second;
        s[i].first = s[i].second % T;
    }
    s[++n] = make_pair(X % T, X);
    for(int i = 1; i <= m; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(s + 1, s + n + 1);
    sort(a + 1, a + m + 1);
    for(int i = 1; i <= m; ++i) pref[i] = pref[i - 1] + a[i].second;
    a[m + 1].first = INF;
    int p = 1;
    add(0, 0);
    for(int i = 1; i <= m; ++i) {
        dp[i] = dp[i - 1] + (long long) W * (X / T + (X % T >= a[i].first));
        int mn = INF;
        while(p <= n && s[p].first < a[i].first) ++p;
        while(p <= n && s[p].first < a[i + 1].first) {
            mn = min(mn, s[p].second / T);
            ++p;
        }
        if(mn < INF) {
            long long val = query(mn) + (long long) W * mn * i + pref[i];
            dp[i] = min(dp[i], val);
        }
        add((long long) W * -i, dp[i] -pref[i]);
    }
    cout << dp[m] + (long long) W * (X / T + 1);
    return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int32_t main()':
coach.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:51:5: note: in expansion of macro 'file'
   51 |     file("A") else file("task");
      |     ^~~~
coach.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:51:5: note: in expansion of macro 'file'
   51 |     file("A") else file("task");
      |     ^~~~
coach.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:51:20: note: in expansion of macro 'file'
   51 |     file("A") else file("task");
      |                    ^~~~
coach.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:51:20: note: in expansion of macro 'file'
   51 |     file("A") else file("task");
      |                    ^~~~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29