제출 #712646

#제출 시각아이디문제언어결과실행 시간메모리
712646minhnhatnoeAliens (IOI16_aliens)C++17
0 / 100
1 ms224 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll sq(ll a) {return a * a;} pair<ll, int> alien_solve(const vector<pair<ll, ll>> &p, ll cost){ vector<pair<ll, int>> dp(p.size()); for (int i=0; i<dp.size(); i++){ dp[i] = make_pair(sq(p[i].second - p[0].first + 1) + cost, 1); for (int j=1; j<=i; j++){ ll value = dp[j-1].first + sq(p[i].second - p[j].first + 1) - sq(max(0LL, p[j-1].second - p[j].first + 1)) + cost; int used = dp[j-1].second + 1; dp[i] = min(dp[i], make_pair(value, used)); } } return dp.back(); } vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){ sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){ return make_pair(a.first, -a.second) < make_pair(b.first, -b.second); }); vector<pair<ll, ll>> r; r.reserve(p.size()); for (const pair<ll, ll> &a: p){ if (r.size() && a.second <= r.back().second) continue; r.push_back(a); } return r; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){ vector<pair<ll, ll>> p(n); for (int i=0; i<n; i++) p[i] = minmax(r[i], c[i]); // p = simplify(p); ll bl = 0, br = 1e18; while (bl < br){ ll bm = (bl + br)>>1; if (alien_solve(p, bm).second > k) bl = bm + 1; else br = bm; } pair<ll, int> result = alien_solve(p, bl); return result.first - result.second * bl; }

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

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<dp.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...