제출 #681801

#제출 시각아이디문제언어결과실행 시간메모리
681801cadmiumskyAliens (IOI16_aliens)C++14
100 / 100
1125 ms70664 KiB
#include "aliens.h" #include <bits/stdc++.h> #warning fa cu ll using namespace std; using ll = long long; #define int ll #define sz(x) (int)(x).size() const int nmax = 1e6 + 5; struct line { int chosen = 0; ll dp = 0, b = (ll)nmax * nmax; line(int x = 0, ll y = (ll)nmax * nmax, ll z = (ll)nmax * nmax): chosen(x), dp(y), b(z) {;} ll operator()(const ll& x) const { return b * x + dp; } bool operator()(const line& form, const line& cand) const { return (dp - form.dp) * (cand.b - b) > (dp - cand.dp) * (form.b - b) || ((dp - form.dp) * (cand.b - b) == (dp - cand.dp) * (form.b - b) && (b < cand.b || (b == cand.b && dp < cand.dp))); } }; struct CHT { line cht[nmax]; int ptr, lim; struct undo_info { line last; int ptrlast; int lstptr; int lstlim; undo_info(line a, int x, int y, int z): last(a), ptrlast(x), lstptr(y), lstlim(z) {;} }; vector<undo_info> undost; int getT() { return sz(undost); } void push(line nv) { undost.emplace_back(line(), 0, ptr, lim); while(lim > 1 && nv(cht[lim - 2], cht[lim - 1])) lim--; undost.back().last = cht[lim]; undost.back().ptrlast = lim; cht[lim++] = nv; ptr = min(lim - 1, ptr); } void undo() { cht[undost.back().ptrlast] = undost.back().last; ptr = undost.back().lstptr; lim = undost.back().lstlim; undost.pop_back(); //cerr << "? " << lim << '\n'; } void undo(int T) { assert(T >= 0); while(getT() > T) undo(); } line query(int x) { // blea?? while(ptr < lim - 1 && cht[ptr + 1](x) < cht[ptr](x)) ptr++; //cerr << x << ' ' << cht[ptr](x) << '\t'; //for(int i = 0; i < lim; i++) //cerr << cht[i](x) << ' '; //cerr << '\n'; return cht[ptr]; } void init() { undost.clear(); ptr = 0; lim = 1; cht[0] = line(0, 0, 0); undost.reserve(nmax); } } cht; ll p2(ll x) { return x * x; } line calculate(const vector<int>& height, ll C) { cht.init(); vector<ll> dp(sz(height)); vector<int> chosen(sz(height)), altern = height, st; st.reserve(sz(height)); st.emplace_back(0); for(int i = 1; i < sz(altern); i++) altern[i] -= i; //for(auto x : height) //cerr << x << ' '; //cerr << '\n'; //for(auto x : altern) //cerr << x << ' '; //cerr << '\n'; for(int i = 1; i < sz(height); i++) { while(altern[st.back()] < altern[i]) (height[st.back()]? cht.undo() : void()), st.pop_back(); if(height[i] != 0) { cht.push(line(chosen[st.back()], (ll)dp[st.back()] - p2(st.back()) - (ll)2 * st.back() * (altern[i]), (ll)2 * (altern[i]))); auto best = cht.query(i); dp[i] = best(i) + p2(i) + C; chosen[i] = best.chosen + 1; } else { chosen[i] = chosen[i - 1], dp[i] = dp[i - 1]; } //cerr << dp[i] << ' '; st.push_back(i); //for(auto x : st) cerr << x << ' '; //cerr << "\n---\n"; //cerr << dp[i] << '\n'; } //cerr << '\n'; return line{chosen.back(), dp.back(), 0}; } ll smenufromaliens(const vector<int>& height, int k) { ll lim = -1; for(ll i = (1LL << 40); i > 0; i >>= 1) { if(calculate(height, lim + i).chosen > k) lim += i; } return lim + 1; } ll take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) { if(n == 0) return 0; vector<int> height(m + 1); height[0] = m + 5; for(int i = 0; i < n; i++) r[i]++, c[i]++, height[max(r[i], c[i])] = max(height[max(r[i], c[i])], (ll)abs(r[i] - c[i]) + 1); while(height.back() == 0) height.pop_back(); int lim = smenufromaliens(height, k); //int lim = 0; auto lol = calculate(height, lim); //cerr << lim << ' ' << lol.dp << ' ' << lol.chosen << ' ' << k << '\n'; return (ll)lol.dp - (ll)lim * k; } #undef int

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

aliens.cpp:4:2: warning: #warning fa cu ll [-Wcpp]
    4 | #warning fa cu ll
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...