Submission #336784

#TimeUsernameProblemLanguageResultExecution timeMemory
336784lovro_nidogon1Cover (COCI18_cover)C++14
120 / 120
5 ms620 KiB
#include<bits/stdc++.h> #define breturn return #define ll long long using namespace std; vector<pair<ll, ll> > kor, hull, bruh; pair<ll, ll> poc; ll n, a, b, c, dp[5002]; bool ccw(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) { // cout << a.first << " " << a.second << " - " << b.first << " " << b.second << " - " << c.first << " " << c.second << '\n'; if(a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0) breturn true; else breturn false; } int main() { cin >> n; c = -1; for(ll i = 0; i < n; i++) { cin >> a >>b; a = abs(a), b = abs(b); kor.push_back({a, b}); } if(n == 1) breturn cout << a * b * 4<< '\n', 0; sort(kor.begin(), kor.end()), reverse(kor.begin(), kor.end()); hull.push_back(kor[0]); for(ll i = 1; i < kor.size(); i++) { if(kor[i].second > hull[hull.size() - 1].second and kor[i].first < hull[hull.size() - 1].first) hull.push_back(kor[i]); } reverse(hull.begin(), hull.end()); dp[0] = 0; for(ll i = 0; i < hull.size(); i++) { bruh.push_back({hull[i].second, dp[i]}); dp[i + 1] = 1000000000000000000; for(ll j = 0; j < bruh.size(); j++) dp[i + 1] = min(dp[i + 1], bruh[j].first * hull[i].first + bruh[j].second); } cout << dp[hull.size()] * 4; }

Compilation message (stderr)

cover.cpp: In function 'int main()':
cover.cpp:24:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i = 1; i < kor.size(); i++) {
      |                ~~^~~~~~~~~~~~
cover.cpp:29:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(ll i = 0; i < hull.size(); i++) {
      |                ~~^~~~~~~~~~~~~
cover.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(ll j = 0; j < bruh.size(); j++) dp[i + 1] = min(dp[i + 1], bruh[j].first * hull[i].first + bruh[j].second);
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...