# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
530865 | cpp219 | Cover (COCI18_cover) | C++17 | 3 ms | 844 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 ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e3 + 9;
const ll inf = 1e18 + 7;
const ll base = 31;
ll n,sz,dp[N];
vector<ll> num;
vector<LL> useful;
ll Find(ll x){
return lower_bound(num.begin(),num.end(),x) - num.begin();
}
LL st[4*N],a[N];
ll f(LL x,ll v){
return x.fs*num[v] + x.sc;
}
void add(ll id,ll l,ll r,LL x){
ll mid = (l + r)/2;
ll c1 = f(x,l) < f(st[id],l);
ll c2 = f(x,mid) < f(st[id],mid);
if (c2) swap(x,st[id]);
if (l == r) return;
if (c1 != c2) add(id*2,l,mid,x);
else add(id*2 + 1,mid + 1,r,x);
}
ll Get(ll id,ll l,ll r,ll v){
ll mid = (l + r)/2,res = f(st[id],v);
if (l == r) return res;
if (v <= mid) return min(res,Get(id*2,l,mid,v));
return min(res,Get(id*2 + 1,mid + 1,r,v));
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n; num.push_back(-inf);
for (ll i = 1;i <= n;i++){
cin>>a[i].fs>>a[i].sc;
a[i].fs = abs(a[i].fs); a[i].sc = abs(a[i].sc);
num.push_back(a[i].fs);
}
for (ll i = 1;i < 4*N;i++) st[i] = {0,inf};
sort(num.begin(),num.end()); sort(a + 1,a + n + 1);
num.resize(unique(num.begin(),num.end()) - num.begin()); sz = num.size() - 1;
ll mx = 0;
for (ll i = n;i > 0;i--){
if (a[i].sc <= mx) continue;
useful.push_back(a[i]); mx = a[i].sc;
}
sort(useful.begin(),useful.end()); //debug(useful.size());
for (ll i = 0;i < useful.size();i++){
LL now = useful[i];
if (i > 0) add(1,1,sz,{4*now.sc,dp[i - 1]});
else add(1,1,sz,{4*now.sc,0});
dp[i] = Get(1,1,sz,Find(now.fs));
}
debug(dp[useful.size() - 1]);
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |