제출 #70870

#제출 시각아이디문제언어결과실행 시간메모리
70870aquablitz11Aliens (IOI16_aliens)C++14
4 / 100
4 ms624 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; using ll = long long; using pli = pair<ll, int>; using pii = pair<int, int>; #define F first #define S second struct CHT { struct line { ll m, c; int cnt; line(ll m, ll c, int cnt) : m(m), c(c), cnt(cnt) {} ll get(ll x) { return m*x + c; } }; bool bad(line l1, line l2, line l3) { return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m); } vector<line> f; int idx; void update(ll m, ll c, int cnt) { line l(m, c, cnt); while (f.size() > 1 && bad(f[f.size()-2], f[f.size()-1], l)) f.pop_back(); f.push_back(l); } pli query(ll x) { while (idx < f.size()-1 && f[idx].get(x) >= f[idx+1].get(x)) ++idx; return pli(f[idx].get(x), f[idx].cnt); } void clear() { f.clear(); idx = 0; } } cht; int n; vector<pii> A; void compress() { sort(A.begin(), A.end(), [&] (pii a, pii b) { return pii(a.F, -a.S) < pii(b.F, -b.S); }); vector<pii> ret; int en = -1; for (auto x : A) if (x.S > en) ret.push_back(x), en = x.S; A = ret; n = A.size(); A.insert(A.begin(), pii(-1e7, -1e7)); } inline ll sq(ll x) { return x*x; } pli solve(ll C) { vector<pli> dp(n+1); cht.clear(); dp[0] = pli(0, 0); for (int i = 1; i <= n; ++i) { cht.update(-2*A[i].F+2, sq(A[i].F-1)+dp[i-1].F-sq(max(0, A[i-1].S-A[i].F+1)), dp[i-1].S); pli q = cht.query(A[i].S); dp[i] = pli(q.F + sq(A[i].S) + C, q.S+1); } return dp[n]; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; ++i) A.push_back(minmax(r[i], c[i])); compress(); ll b = 0, e = 1e17; while (b < e) { ll v = (b+e)/2; if (solve(v).S <= k) e = v; else b = v+1; } return solve(b).F - b*k; }

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

aliens.cpp: In member function 'pli CHT::query(ll)':
aliens.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (idx < f.size()-1 && f[idx].get(x) >= f[idx+1].get(x))
                ~~~~^~~~~~~~~~~~
#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...