제출 #82133

#제출 시각아이디문제언어결과실행 시간메모리
82133BatrrAliens (IOI16_aliens)C++14
4 / 100
3 ms724 KiB
#include "aliens.h" #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; const int N = (int)1e5 + 123, inf = 1e9; const ll INF = 1e18; using namespace std; struct line{ ll k, b; double X; int cnt; double intersect(line a){ return -1.0 * (a.b - b) / (a.k - k); } }; struct cvh{ vector< line > v; int ptr = 0; void add(line x){ while(v.size() > 1){ line a = v[v.size() - 1]; line b = v[v.size() - 2]; if(x.intersect(a) < x.intersect(b)) v.pop_back(); else break; } if(v.empty()){ x.X = -INF; }else{ line a = v.back(); x.X = x.intersect(a); } v.pb(x); } pair<ll, ll> get(ll x, ll add){ if(v.empty()) return {INF, 1}; ptr = min(ptr, (int)v.size()); while(ptr < v.size() && v[ptr].X < x) ptr++; pair< ll, ll> res; res.f = v[ptr - 1].k * x + v[ptr - 1].b; res.s = v[ptr - 1].cnt + 1; res.f += add; return res; } }; ll sqr(ll x){ return x * x; } pair<ll ,ll> get(ll C, vector< pair<int, int> > &arr){ int n = arr.size(); vector< pair<ll, ll> > dp(n); vector< line > ln(n, {0, INF}); cvh btr; for(int i = 0; i < n; i++){ dp[i] = min( mp(sqr(arr[i].s - arr[0].f + 1), 1ll) , btr.get(arr[i].s, sqr(arr[i].s)) ); dp[i].f += C; if(i != n - 1){ ll b = dp[i].f + sqr(arr[i + 1].f - 1) - sqr(max(0, arr[i].s - arr[i + 1].f + 1)); ll k = - 2 * (arr[i + 1].f - 1); ln[i].k = k; ln[i].b = b; ln[i].cnt = dp[i].s; btr.add(ln[i]); } } dp[n - 1].f -= C * dp[n - 1].s; return dp[n - 1]; } ll take_photos(int n, int m, int k, vector<int> row, vector<int> col) { vector< pii > arr, tmp; for(int i = 0; i < n; i++){ int l, r; l = row[i]; r = col[i]; if(l > r) swap(l, r); tmp.pb({l, -r}); } sort(tmp.begin(), tmp.end()); for(int i = 0, mx = -1; i < n; i++){ int l = tmp[i].f; int r = -tmp[i].s; if(r <= mx) continue; mx = r; arr.pb({l, r}); } n = arr.size(); if(n < k) k = n; ll l = 0, r = 1e15; while(l <= r){ ll m = (l + r) / 2; int x = get(m, arr).s; if(x > k) l = m + 1; else r = m - 1; } r++; return get(r, arr).f; }

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

aliens.cpp: In member function 'std::pair<long long int, long long int> cvh::get(ll, ll)':
aliens.cpp:52:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < v.size() && v[ptr].X < 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...