Submission #530865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
530865	2022-02-27T03:02:14 Z	cpp219	Cover (COCI18_cover)	C++17	120 / 120	3 ms	844 KB

cover

#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

cover.cpp: In function 'int main()':
cover.cpp:63:21: 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]
   63 |     for (ll i = 0;i < useful.size();i++){
      |                   ~~^~~~~~~~~~~~~~~
cover.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	1 ms	588 KB	Output is correct
3	Correct	1 ms	588 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	588 KB	Output is correct
7	Correct	1 ms	588 KB	Output is correct
8	Correct	1 ms	588 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	3 ms	844 KB	Output is correct