제출 #1067538

#제출 시각아이디문제언어결과실행 시간메모리
1067538andrei_iorgulescuAliens (IOI16_aliens)C++14
4 / 100
1 ms600 KiB
#include <bits/stdc++.h> #include "aliens.h" #warning That's not FB, that's my FB using namespace std; using ll = long long; using ld = long double; const ld eps = 0.5d; int n, m; vector<int> l, r; bool cmp(pair<int,int> A, pair<int,int> B) { if (A.first != B.first) return A.first < B.first; return A.second > B.second; } void norma_intvs() { vector<pair<int,int>> vp; for (int i = 0; i < l.size(); i++) vp.push_back({l[i], r[i]}); sort(vp.begin(), vp.end(), cmp); l.clear(); r.clear(); int rmax = -1; for (auto it : vp) { if (it.second > rmax) { rmax = it.second; l.push_back(it.first); r.push_back(it.second); } } } struct ura { ld val; int cate; }; ura dp[200005]; struct dreapta { ld offset, panta; int idx; }; ld inters(dreapta d1, dreapta d2) { return (d2.offset - d1.offset) / (d1.panta - d2.panta); } deque<dreapta> dq; void baga(dreapta d) { dq.push_back(d); while (dq.size() >= 3) { dreapta d1 = dq.back(); dq.pop_back(); dreapta d2 = dq.back(); dq.pop_back(); dreapta d3 = dq.back(); dq.pop_back(); if (inters(d2, d3) >= inters(d1, d2)) { dq.push_back(d3); dq.push_back(d1); } else { dq.push_back(d3); dq.push_back(d2); dq.push_back(d1); break; } } } dreapta query(ld x) { while (dq.size() >= 2) { dreapta d1 = dq.front(); dq.pop_front(); dreapta d2 = dq.front(); dq.pop_front(); if (inters(d1, d2) <= x) dq.push_front(d2); else { dq.push_front(d2); dq.push_front(d1); break; } } return dq.front(); } void solve(ld cost) { dp[0].val = dp[0].cate = 0; dq.clear(); for (int i = 1; i <= n; i++) { dreapta cur; cur.idx = i; cur.offset = dp[i - 1].val + (ld)l[i] * (ld)l[i]; if (i != 1 and l[i] <= r[i - 1]) cur.offset -= (ld)(r[i - 1] - l[i] + 1) * (ld)(r[i - 1] - l[i] + 1); cur.panta = -l[i]; baga(cur); dreapta sol = query(2 * r[i] + 2); dp[i].cate = 1 + dp[sol.idx - 1].cate; dp[i].val = cost + (ld)(r[i] + 1) * (ld)(r[i] + 1) + sol.offset + (ld)(2 * r[i] + 2) * sol.panta; } } ll take_photos(int N, int M, int k, vector<int> R, vector<int> C) { n = N, m = M; for (int i = 0; i < n; i++) { l.push_back(min(R[i],C[i])); r.push_back(max(R[i],C[i])); } norma_intvs(); n = l.size(); vector<int> newl = {0}; for (auto it : l) newl.push_back(it); l = newl; vector<int> newr = {0}; for (auto it : r) newr.push_back(it); r = newr; ld st = (ll)1e6 * (ll)1e6; ld pas = 1ll << 39; while (pas >= eps) { if (st - pas >= 0) { solve(st - pas); if (dp[n].cate <= k) st -= pas; } pas /= 2.0d; } solve(st); ld ans = dp[n].val - st * (ld)k; if (ans - (ll)ans <= 0.5d) return (ll)ans; return (ll)ans + 1; }

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

aliens.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
aliens.cpp: In function 'void norma_intvs()':
aliens.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
#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...