제출 #241491

#제출 시각아이디문제언어결과실행 시간메모리
241491osaaateiasavtnlLong Distance Coach (JOI17_coach)C++17
100 / 100
529 ms42148 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int N = 2e5+7; const ll inf = 5e18; bool Q = 0; struct Line { mutable ll m, b, x; bool operator < (const Line ot) const { return Q ? x < ot.x : m < ot.m; } }; ll ceil (ll a, ll b) { if (a < 0 != b < 0) return a / b; return (abs(a) + abs(b) - 1) / abs(b); } ll intersection (const Line &p, const Line &q) { return ceil(q.b - p.b, p.m - q.m); } struct Hull : multiset<Line> { bool valid (auto it) { if (it == begin()) { auto sig = it; sig++; if (sig != end()) sig->x = intersection(*it, *sig); return it->x = -inf; } auto ant = it, sig = it; ant--, sig++; if (sig == end()) { it->x = intersection(*it, *ant); return 1; } ll x = intersection(*it, *ant); ll y = intersection(*it, *sig); if (x > y) return 0; it->x = x, sig->x = y; return 1; } void add (ll m, ll b) { m = -m; b = -b; auto it = lower_bound({m, b, -inf}); if (it != end() && it->m == m) { if (it->b > b) return; it->b = b; } else { it = insert({m, b, -inf}); } if (!valid(it)) { erase(it); return; } auto ant = it; while (ant != begin()) { if (valid(--ant)) break; erase(ant); if (it == begin()) { it->x = -inf; break; } ant = it; } auto sig = it; sig++; while (sig != end() && !valid(sig)) erase(sig++); } ll query (ll x) { if (empty()) return -inf; Q = 1; auto it = upper_bound({0, 0, x}); it--; Q = 0; return x * it->m + it->b; } } h; int pref[N]; signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int x, n, m, w, t; cin >> x >> n >> m >> w >> t; //first - d, second - c vector <int> s(n); for (int i = 0; i < n; ++i) cin >> s[i]; sort(all(s)); s.app(x); vector <ii> a(m); for (int i = 0; i < m; ++i) cin >> a[i].f >> a[i].s; sort(all(a)); reverse(all(a)); a.insert(a.begin(), mp(0, 0)); map <int, int> pos; for (int i = 0; i < a.size(); ++i) pos[a[i].f] = i; vector <int> c; for (auto e : a) c.app(e.f); sort(all(c)); vector <int> last(s.size()), mem(a.size(), s.size()); for (int i = 0; i < s.size(); ++i) { int p = lower_bound(all(c), s[i]%t) - c.begin(); p = (p - 1 + c.size()) % c.size(); last[i] = pos[c[p]]; mem[last[i]] = min(mem[last[i]], i); } vector <int> dp(a.size()+1); dp[0] = (x/t+1)*w; dp[1] = dp[0]+(x/t+(a[1].f<=(x%t)))*w; for (int i = 0; i < a.size(); ++i) pref[i+1] = pref[i] + a[i].s; for (int j = 2; j <= a.size(); ++j) { if (mem[j-1] != s.size()) { int k = s[mem[j-1]]/t*w; int x = -h.query(j-2); if (x != inf) { h.add(k, x-k*(j-2)); } int i = j - 2; h.add(k, dp[i]-pref[i+1]-i*k); } int save = 0; if (j < a.size()) save = (x/t+(a[j].f<=(x%t)))*w; int mn = -h.query(j-1)+pref[j]; mn = min(mn, dp[j-1]); dp[j] = mn + save; } cout << (int)dp[a.size()] << endl; }

컴파일 시 표준 에러 (stderr) 메시지

coach.cpp: In function 'long long int ceil(long long int, long long int)':
coach.cpp:26:11: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
     if (a < 0 != b < 0) return a / b;
         ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:151:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 2; j <= a.size(); ++j) {
                     ~~^~~~~~~~~~~
coach.cpp:152:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (mem[j-1] != s.size()) {
coach.cpp:162:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < a.size())
             ~~^~~~~~~~~~
coach.cpp: In instantiation of 'bool Hull::valid(auto:1) [with auto:1 = std::_Rb_tree_const_iterator<Line>]':
coach.cpp:70:22:   required from here
coach.cpp:38:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             return it->x = -inf;
                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...