# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1082373 | mimi | Cover (COCI18_cover) | C++17 | 14 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <ll,ll>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const ll maxn = 2e5+5, mod = 1e9+7, N = 10;
const ll inf = 1e18L+3;
ll n;
pii a[maxn];
ll dp[maxn];
bool cmp(pii x, pii y)
{
if(x.ff!=y.ff) return x.ff<y.ff;
return x.ss>y.ss;
}
void input()
{
cin>>n;
for(ll i=1;i<=n;++i)
{
cin>>a[i].ff>>a[i].ss;
a[i].ff = abs(a[i].ff);
a[i].ss = abs(a[i].ss);
}
sort(a+1,a+n+1,cmp);
// for(ll i=1;i<=n;++i) cout<<a[i]<<el;
}
void solve()
{
fill(dp+1,dp+n+1,inf);
dp[1] = a[1].ff*a[1].ss;
for(ll i=2;i<=n;++i)
{
ll mx = a[i].ss;
for(ll j=i;j>0;--j)
{
mx = max(mx,a[j].ss);
dp[i] = min(dp[i],dp[j-1]+mx*a[i].ff);
}
}
cout<<dp[n]*4;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll test = 1;
// cin>>test;
while(test-->0)
{
input();
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |