oj.uz

Submission #600628

# Submission time Handle Problem Language Result Execution time Memory
600628 2022-07-21T06:29:05 Z 이동현(#8470) Long Distance Coach (JOI17_coach) C++17
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NS = (int)2e5 + 4;
int x, n, m, w, t;
int r[NS];
int s[NS];
vector<int> peo[NS];
int dp[NS], vala[NS], valb[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> x >> n >> m >> w >> t;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    ++n; s[n] = x;
    for(int i = 1; i <= m; ++i){
        peo[i].resize(2);
        cin >> peo[i][0] >> peo[i][1];
    }
    sort(s + 1, s + n + 1, [&](int&x, int&y){return x % t < y % t;});
    sort(peo + 1, peo + m + 1);
    int pp = 0;
    for(int i = 1; i <= n; ++i){
        while(pp + 1 <= m && peo[pp + 1][0] < s[i] % t){
            ++pp;
        }
        r[i] = pp;
    }
    auto eat = [&](int all, int me)->int{
        if(all >= me) return (all - me) / t + 1;
        return 0;
    };
    int ans = (int)1e18;
    for(int i = 1; i <= n; ++i){
        dp[i] = (int)1e18;
        for(int j = 0; j < i; ++j){
            int sum = 0;
            for(int k = r[j] + 1; k <= r[i]; ++k){
                vala[k] = w * eat(x, peo[k][0]);
                valb[k] = peo[k][1] + w * eat(s[i] / t * t, peo[k][0]);
                sum += vala[k];
            }
            for(int k = r[i]; k > r[j]; --k){
                sum += valb[k] - vala[k];
                dp[i] = min(dp[i], dp[j] + sum);
            }
        }
        int nval = dp[i];
        for(int j = r[i] + 1; j <= m; ++j){
            nval += w * eat(x, peo[j][0]);
        }
        ans = min(ans, nval);
    }
    ans += w * eat(x, 0);
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -