oj.uz

Submission #17414

# Submission time Handle Problem Language Result Execution time Memory
17414 2015-12-01T11:25:49 Z gs14004 Palembang Bridges (APIO15_bridge) C++14
0 / 100
 0 ms 4300 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
 
struct pt{
    ll x,y;
    bool operator<(const pt& r)const{
        return x+y<r.x+r.y;
    }
};
 
int K,N,sz;
ll base,ans,sum;
ll L[100010],R[100010];
pt a[100010];
 
priority_queue<ll> lo;
priority_queue<ll,vector<ll>,greater<ll> > hi;
 
void push(int x){
    if(!hi.empty()&&x>=hi.top())hi.push(x);
    else lo.push(x);
    ll t;
    while(hi.size()+1<lo.size()){
        t=lo.top();lo.pop();
        hi.push(t);
    }
    while(hi.size()>lo.size()+1){
        t=hi.top();hi.pop();
        lo.push(t);
    }
}
 
void f(ll s[]){
    for(int i=0;i<sz;i++){
        push(a[i].x);
        push(a[i].y);
        //printf("%lld %lld\n",lo.top(),hi.top());
        int mid=(lo.top()+hi.top())/2;
        for(int j=0;j<=i;j++){
            s[i]+=abs(a[j].x-mid);
            s[i]+=abs(a[j].y-mid);
        }
    }
}
 
int main(){
    //freopen("bridge.in","r",stdin);
 
    scanf("%d%d ",&K,&N);
    char tx,ty;
    ll x,y;
    for(int i=0;i<N;i++){
      char tx[4], ty[4];
        scanf("%s %lld %s %lld ",tx,&x,ty,&y);
        if(*tx==*ty){
            base+=y-x-1;
        }else{
            a[sz++]=pt{x,y};
        }
    }
    base+=N;
 
    sort(a,a+sz);
 
    f(L);
    if(K==1){
        printf("%lld",L[sz-1]+base);
        return 0;
    }
    reverse(a,a+sz);
    f(R);
 
    ans=1e18;
    for(int i=0;i<sz-1;i++){
        ans=min(ans,L[i]+R[sz-2-i]);
    }
 
    printf("%lld",ans+base);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:53:10: warning: unused variable 'tx' [-Wunused-variable]
     char tx,ty;
          ^
bridge.cpp:53:13: warning: unused variable 'ty' [-Wunused-variable]
     char tx,ty;
             ^
bridge.cpp:52:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d ",&K,&N);
                         ^
bridge.cpp:57:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %lld %s %lld ",tx,&x,ty,&y);
                                              ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4300 KB Output is correct
2 Incorrect 0 ms 4300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4300 KB Output is correct
2 Incorrect 0 ms 4300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -