Submission #877491

#TimeUsernameProblemLanguageResultExecution timeMemory
877491noiaintCover (COCI18_cover)C++17
120 / 120
4 ms2616 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #define file "" #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = (int)1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int oo = 1e9; const long long ooo = 1e18; template<class X, class Y> bool mini(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maxi(X &a, Y b) { return a < b ? (a = b, true) : false; } void add(int &a, int b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int n; pair<int, int> a[N]; int f[N]; void process() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i].fi >> a[i].se; a[i].fi = abs(a[i].fi); a[i].se = abs(a[i].se); } sort(a + 1, a + n + 1); vector<int> st; for (int i = 1; i <= n; ++i) { while (st.size() && a[st.back()].se <= a[i].se) st.pop_back(); st.push_back(i); } n = (int) st.size(); for (int i = 1; i <= n; ++i) { f[i] = 1e18; for (int j = 1; j <= i; ++j) mini(f[i], f[j - 1] + a[st[i - 1]].fi * a[st[j - 1]].se); } cout << f[n] * 4; } signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); // freopen(file".out", "w", stdout); #endif int tc = 1; // cin >> tc; while (tc--) { process(); } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...