oj.uz

Submission #600926

# Submission time Handle Problem Language Result Execution time Memory
600926 2022-07-21T09:13:31 Z 반딧불(#8467) Long Distance Coach (JOI17_coach) C++17
0 / 100
 4 ms 4996 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#ifdef TEST
typedef long long BigInt;
#else
typedef __int128 BigInt;
#endif // TEST

struct Person{
    ll off, cost;
    Person(){}
    Person(ll off, ll cost): off(off), cost(cost){}
    bool operator<(const Person &r)const{
        return off < r.off;
    }
};

struct Query{
    int st;
    ll constant, slope;
    Query(int st, ll constant, ll slope): st(st), constant(constant), slope(slope){}
};

ll X, W, T;
int n, k;
ll arr[200002];
Person person[200002];
ll DP[200002], adj[200002], costSum[200002];
ll ans = 9e18;
vector<Query> queryVec[200002];
vector<pair<int, ll> > convexHull;

ll findVal(int s, int e, ll slope){
    int l = lower_bound(convexHull.begin(), convexHull.end(), make_pair(s, LLONG_MIN)) - convexHull.begin();
    int r = (int)convexHull.size()-1;
    while(r-l>=3){
        int m = (l+r)/2;
        if(convexHull[m].second - convexHull[m].first * slope <= convexHull[m+1].second - convexHull[m].first * slope)
            r = m+1;
        else l = m;
    }
    ll ret = LLONG_MAX;
    for(int i=l; i<=r; i++) ret = min(ret, convexHull[i].second - convexHull[i].first * slope);
    return ret;
}

long double calcSlope(pair<int, ll> p1, pair<int, ll> p2){
    return (long double)(p2.second - p1.second) / (p2.first - p1.first);
}

bool canInsert(BigInt x, BigInt y){
    BigInt a = convexHull[convexHull.size()-2].first, b = convexHull[convexHull.size()-2].second;
    BigInt c = convexHull.back().first, d = convexHull.back().second;
    return (c-a)*(y-b) - (d-b)*(x-a) > 0;
}

void updatePoint(ll x, ll y){
    while(convexHull.size() >= 2 && !canInsert(x, y)){
        convexHull.pop_back();
    }
    convexHull.push_back(make_pair(x, y));
}

int main(){
    scanf("%lld %d %d %lld %lld", &X, &k, &n, &W, &T);
    for(int i=1; i<=k; i++) scanf("%lld", &arr[i]);
    sort(arr+1, arr+k+1);
    arr[++k] = X;
    for(int i=1; i<=n; i++) scanf("%lld %lld", &person[i].off, &person[i].cost);
    sort(person+1, person+n+1);

    DP[0] = (X / T + 1) * W;
    for(int i=1; i<=n; i++){
        DP[i] = 9e18;
        costSum[i] = costSum[i-1] + person[i].cost;
        adj[i] = -costSum[i];
    }

    for(int i=1; i<=k; i++){
        ll prv = arr[i-1], now = arr[i];
        int st = 1, en = lower_bound(person+1, person+n+1, Person(now%T, 0)) - person - 1;
        if(prv%T == now%T) st = upper_bound(person+1, person+n+1, Person(prv%T, 0)) - person;
        if(st > en) continue;
        ll slope = now/T*W;
        queryVec[en].push_back(Query(st-1, costSum[en] + slope*en, slope));
    }

    convexHull.push_back(make_pair(0, DP[0]));
    for(int i=1; i<=n; i++){
        DP[i] = DP[i-1] + ((X - person[i].off + T) / T * W);
        for(Query query: queryVec[i]){
            ll tmp = findVal(query.st, i-1, query.slope);
            DP[i] = min(DP[i], tmp + query.constant);
        }
        updatePoint(i, DP[i] + adj[i]);
    }
    printf("%lld", DP[n]);
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%lld %d %d %lld %lld", &X, &k, &n, &W, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:69:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     for(int i=1; i<=k; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
coach.cpp:72:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     for(int i=1; i<=n; i++) scanf("%lld %lld", &person[i].off, &person[i].cost);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4996 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4960 KB Output is correct
15 Incorrect 3 ms 4948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4996 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4960 KB Output is correct
15 Incorrect 3 ms 4948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4996 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4960 KB Output is correct
15 Incorrect 3 ms 4948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4996 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4960 KB Output is correct
15 Incorrect 3 ms 4948 KB Output isn't correct
16 Halted 0 ms 0 KB -