Submission #47997

#	Time	Username	Problem	Language	Result	Execution time	Memory
47997		yusufake	Palembang Bridges (APIO15_bridge)	C++98	31 / 100	346 ms	2300 KiB

bridge

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

ll A[N],B[N],n,k,nn,t,w,i,x,y,l,m1,m2,r,ans,zz=44;
char c1,c2;

ll g(ll a, ll b){
	ll t=0,i;
	for(i=1;i<=nn;i++)
		t += min( abs(a - A[i]) + abs(a - B[i]) , b == -1 ? 1LL<<55 : abs(b - A[i]) + abs(b - B[i]) ) + 1;
	return t;
}

ll f(ll a){
    if(k == 1) return g(a,-1);
    ll i, l=a+1,m1,m2,r=1LL<<30;
    for(i=zz+zz; i--;){
        m1 = l + (r-l+1)/3;
        m2 = r - (r-l+1)/3;
        if(g(a,m1) > g(a,m2)) l = m1;
        else r = m2;
    }
    ll mn = 1LL<<55;
    for(i=l-zz; i<l+zz; i++)
        mn = min(mn , g(a,max(a+1,i)));
    return mn;
}

int main(){
    cin >> k >> n;
	for(i=1;i<=n;i++){
		scanf(" %c%lld %c%lld",&c1,&x,&c2,&y);
        if(c1 == c2) { ans += abs(y-x); continue; }
		A[++nn] = x; B[nn] = y;
	}

    l=0; r=1LL<<30;
	for(i=zz+zz; i--;){
    //    cout << l << " " << r << " ss\n";
		m1 = l + (r-l+1)/3;
        m2 = r - (r-l+1)/3;
		if(f(m1) > f(m2)) l = m1;
		else r = m2;
	}
    ll mn = 1LL<<55;
    for(i=l-zz; i<l+zz; i++)
        mn = min(mn , f(i));
   
    cout << ans + mn;
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%lld %c%lld",&c1,&x,&c2,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37