Submission #54203

#TimeUsernameProblemLanguageResultExecution timeMemory
54203ksun48Long Distance Coach (JOI17_coach)C++14
71 / 100
2080 ms19792 KiB
#include <bits/stdc++.h> typedef long long LL; using namespace std; LL cnt(LL m, LL a, LL b, LL T){ a -= m; b -= m; if(b < 0) return 0; a = max(a, 0LL); b = max(b, 0LL); LL f = (a+T-1)/T; LL g = (b)/T; return max(g-f+1, 0LL); } int main(){ cin.sync_with_stdio(0); cin.tie(0); LL X, N, M, W, T; cin >> X >> N >> M >> W >> T; // X = total duration // N = # stops // M = # passenges vector<LL> stop; stop.push_back(0); for(LL i = 0; i < N; i++){ LL s; cin >> s; stop.push_back(s); } stop.push_back(X); sort(stop.begin(), stop.end()); // W = cost vector<pair<LL,LL> > times; LL totalrefundcost = 0; for(LL i = 0; i < M; i++){ LL d, c; cin >> d >> c; times.push_back({d,c}); totalrefundcost += c; } sort(times.begin(), times.end()); vector<LL> t; vector<LL> refundcost; t.push_back(0); refundcost.push_back(0); // but you must always feed the driver for(int i = 0; i < M; i++){ t.push_back(times[i].first); refundcost.push_back(times[i].second); } t.push_back(T); refundcost.push_back(0); // should not use this result vector<LL> dp(refundcost.size(), W*(X+1)); dp[0] = 0; vector<LL> minstopindex(refundcost.size(), stop.size()); for(LL r = 1; r < stop.size(); r++){ LL R = stop[r]; for(int i = 0; i < t.size(); i++){ if(t[i] < (R % T) && (R % T) < t[i+1]){ minstopindex[i] = min(minstopindex[i], r); break; } } } for(int j = 1; j < refundcost.size(); j++){ LL cost = 0; LL idx = stop.size(); for(int i = j-1; i >= 0; i--){ dp[j] = min(dp[j], dp[i] + W * cnt(t[i], 0, X, T) + cost); cost += refundcost[i]; idx = min(idx, minstopindex[i]); if(idx == stop.size()){ cost += W * cnt(t[i], 0, X, T); } else { cost += W * (cnt(t[i], 0, stop[idx], T) - 1); } } } // T = time delay cout << dp[refundcost.size()-1] << '\n'; }

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL r = 1; r < stop.size(); r++){
                ~~^~~~~~~~~~~~~
coach.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < t.size(); i++){
                  ~~^~~~~~~~~~
coach.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 1; j < refundcost.size(); j++){
                 ~~^~~~~~~~~~~~~~~~~~~
coach.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(idx == stop.size()){
       ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...