제출 #1082656

#제출 시각아이디문제언어결과실행 시간메모리
1082656hqminhuwuAliens (IOI16_aliens)C++14
0 / 100
1 ms352 KiB
#include "aliens.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int N = 1e6 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; struct line { ll m, c; ll eval (ll x) { return m * x + c; } ld its (line l) { return (ld) (c - l.c) / (l.m - m); } }; ll sqr (ll x){ return x * x; } ll dp[N], cnt[N]; vector <pll> v; map <ll, ll> z; void calc (ll x){ deque <line> dq; deque <int> dqcnt; dq.push_front({-2 * v[0].st, x + 1 + sqr(v[0].st) - 2 * v[0].st}); dqcnt.push_front(0); forf (i, 0, v.size()){ while (dq.size() >= 2 && dq.back().eval(v[i].nd) > dq[dq.size() - 2].eval(v[i].nd)){ dq.pop_back(); dqcnt.pop_back(); } dp[i] = dq.back().eval(v[i].nd) + sqr(v[i].nd) + 2 * v[i].nd; cnt[i] = dqcnt.back() + 1; if (i == v.size() - 1) return; line cur = {-2 * v[i].st, dp[i] + x + 1 - sqr(max(0ll, v[i].nd - v[i + 1].st + 1)) + sqr(v[i + 1].st) - 2 * v[i + 1].st}; while (dq.size() >= 2 && cur.its(dq[0]) >= dq[0].its(dq[1])){ dq.pop_front(); dqcnt.pop_front(); } dqcnt.push_front(cnt[i]); dq.push_front(cur); } } ll take_photos (int n, int m, int k, vector<int> r, vector<int> c){ forf (i, 0, n){ if (r[i] > c[i]) swap(r[i], c[i]); maxz(z[r[i]], c[i]); } ll mx = 0; for (pll t : z){ if (t.nd > mx){ v.pb(t); mx = t.nd; } } ll l = 0, h = 1ll * m * m; n = v.size() - 1; // for (pii t : v) // cout << t.st << " " << t.nd << "\n"; while (l < h){ ll mid = (l + h) >> 1; calc(mid); //cout << mid << " " << cnt[n] << endl; if (cnt[n] > k) l = mid + 1; else h = mid; } calc(l); //cout << dp[n] << " " << cnt[n] << " " << l << endl;; return dp[n] - k * l; }

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

aliens.cpp: In function 'void calc(ll)':
aliens.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if (i == v.size() - 1) return;
      |             ~~^~~~~~~~~~~~~~~
#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...