제출 #1145085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145085		byunjaewoo	Long Distance Coach (JOI17_coach)	C++20	71 / 100	62 ms	32072 KiB

coach

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=2010;
int x, n, m, w, t, s[N], d[N], c[N], val[N][N], dp[N];
vector<pair<int, int>> vec[N];
pair<int, int> _[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>x>>n>>m>>w>>t;
    for(int i=1; i<=n; i++) cin>>s[i];
    s[0]=-1;
    s[++n]=x;
    for(int i=1; i<=m; i++) cin>>_[i].first>>_[i].second;
    sort(_+1, _+m+1);
    for(int i=1; i<=m; i++) d[i]=_[i].first, c[i]=_[i].second;
    sort(s+1, s+n+1);
    for(int i=0; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            val[i][j]=val[i][j-1]+(s[j]-1+t-d[i])/t-(s[j-1]+t-d[i])/t;
        }
    }
    for(int i=1; i<=n; i++) {
        int l=m+1, r=0;
        if(((s[i]-1)/t)*t>=(s[i-1]+1)) {
            l=1;
            for(int j=1; j<=m; j++) if(d[j]<=(s[i]-1)%t) r=j;
        }
        else {
            for(int j=1; j<=m; j++) {
                if(d[j]>=(s[i-1]+1)%t) l=min(l, j);
                if(d[j]<=(s[i]-1)%t) r=j;
            }
        }
        if(l<=r) vec[r].push_back({l, i});
    }
    for(int i=1; i<=m; i++) {
        dp[i]=dp[i-1]+val[i][n]*w;
        for(auto [l, k]:vec[i]) {
            for(int j=i, sum=0; j>=l; j--) {
                sum+=c[j]+(val[j][k]-1)*w;
                dp[i]=min(dp[i], dp[j-1]+sum);
            }
        }
    }
    cout<<dp[m]+val[0][n]*w;
    return 0;
}

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