oj.uz

Submission #392798

# Submission time Handle Problem Language Result Execution time Memory
392798 2021-04-21T17:22:20 Z hackermub Palembang Bridges (APIO15_bridge) C++17
100 / 100
 327 ms 14388 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define float long double
#define pff pair<float,float>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(),v.end()
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define forn(i,st,n,inc) for(int i=st;i<n;i+=inc)
#define rforn(i,st,n,inc) for(int i=st-1;i>=n;i-=inc)
#define bruh cout<<"\nbruh\n"; exit(0);
#define UB(v,x) upper_bound(all(v),x)
#define LB(v,x) lower_bound(all(v),x)
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pi acos(-1)
const int MOD = 1e9+7;
const int64_t INF64 = INT64_MAX;
const int32_t INF32 = INT32_MAX;


ostream& operator<<(ostream& o,const string& s){
    for(auto c:s) o<<c;
    return o;
}

template<typename F,typename S>
ostream& operator<<(ostream& o,const pair<F,S>& p){
    o<<"["<<p.fi<<","<<p.se<<"]";
    return o;
}

template<typename... T,template<class...> class C>
ostream& operator<<(ostream& o,const C<T...>& v){
    o<<"[";
    int tot=0;
    for(auto x:v){ 
        o<<x;
        if(tot<v.size()-1) o<<",";
        tot++;
    }
    o<<"]";
    return o;
}

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef OFFLINE
clock_t Tm=clock();
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...)
#endif

void init(){
    
}

vector<pll> v;
vector<ll> pre;
multiset<ll> lst,rst;
ll lsum=0,rsum=0;

void insert(int x){
    ll med=size(lst)? *--end(lst):INF32;
    if(x<=med){
        lst.insert(x);
        lsum+=x;
    }else{
        rst.insert(x);
        rsum+=x;
    }
    if(size(lst)>size(rst)+1){
        int now=*--end(lst);
        lst.erase(--end(lst));
        rst.insert(now);
        lsum-=now;
        rsum+=now;
    }else if(size(lst)<size(rst)){
        int now=*begin(rst);
        rst.erase(begin(rst));
        lst.insert(now);
        lsum+=now;
        rsum-=now;
    }
    debug(*--end(lst),lsum,rsum);
}

void solve(){
    int k,n;
    cin>>k>>n;
    ll lol=0;
    for(int i=0;i<n;i++){
        char a,b;
        ll x,y;
        cin>>a>>x>>b>>y;
        if(a==b) lol+=abs(x-y);
        else v.pb({x,y});
    }
    sort(all(v),[](pll a,pll b)->bool{
        return a.fi+a.se<b.fi+b.se;
    });
    int m=size(v);
    if(!m) return void(cout<<lol);
    lol+=m;
    pre.resize(m);
    debug(v);
    for(int i=0;i<m;i++){
        insert(v[i].fi);
        insert(v[i].se);
        pre[i]=rsum-lsum;
    }
    debug(pre);
    ll ans=pre[m-1];
    if(k==2){
        lsum=0,rsum=0;
        lst.clear(),rst.clear();
        for(int i=m-1;i>0;i--){
            insert(v[i].fi);
            insert(v[i].se);
            ans=min(ans,rsum-lsum+pre[i-1]);
        }
    }
    debug(ans,lol);
    cout<<ans+lol;
} 



int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie();
    //If you hack my code , You are gay
    init();
    int T=1;
    //cin>>T;
    //scanf("%d",&T);
    while(T--){
        solve();
        //cout<<"\n";
        //printf("\n");
    }
        //mara kha
    #ifdef OFFLINE
        //cerr<<"Time = "<<(double)(clock()-Tm)/CLOCKS_PER_SEC;
    #endif
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 464 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 83 ms 12736 KB Output is correct
13 Correct 191 ms 14384 KB Output is correct
14 Correct 137 ms 11960 KB Output is correct
15 Correct 79 ms 8580 KB Output is correct
16 Correct 88 ms 13624 KB Output is correct
17 Correct 96 ms 14264 KB Output is correct
18 Correct 85 ms 13944 KB Output is correct
19 Correct 100 ms 14312 KB Output is correct
20 Correct 91 ms 13876 KB Output is correct
21 Correct 99 ms 14080 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 460 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 2 ms 448 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 368 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 452 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 142 ms 12812 KB Output is correct
26 Correct 260 ms 12984 KB Output is correct
27 Correct 322 ms 13752 KB Output is correct
28 Correct 322 ms 14332 KB Output is correct
29 Correct 327 ms 14388 KB Output is correct
30 Correct 120 ms 7680 KB Output is correct
31 Correct 132 ms 13652 KB Output is correct
32 Correct 145 ms 14352 KB Output is correct
33 Correct 138 ms 13880 KB Output is correct
34 Correct 147 ms 14268 KB Output is correct
35 Correct 143 ms 13896 KB Output is correct
36 Correct 150 ms 14160 KB Output is correct
37 Correct 146 ms 12836 KB Output is correct