제출 #60627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60627		istlemin	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1100 ms	4224 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n,k;
vi points;
vector<pii> intervals;

ll getCost(vi bridges){
    ll cost = 0;
    rep(i,0,intervals.size()) {
		ll dist = 1e18;
        rep(j,0,k) {
			if(bridges[j]<0||bridges[j]>=points.size()) return 1e18;
			dist = min(dist,abs(points[bridges[j]]-intervals[i].first)+abs(points[bridges[j]]-intervals[i].second));
        }
        cost += dist;
    }
    return cost;
}

int main(){
	cin.sync_with_stdio(false);
    cin>>k>>n;
    ll ans = 0;
    rep(i,0,n){
		char a,b;
		ll c,d;
		cin>>a>>c>>b>>d;
        if(a==b){
            ans += abs(c-d);
        } else {
			points.push_back(c);
			points.push_back(d);
			intervals.push_back({c,d});
            ans++;
        }
    }

    if(points.size()==0) {
		cout<<ans<<endl;
		return 0;
    }

    sort(all(points));

    ll a = 0;
    ll b = points.size()-1;

    double jump = points.size()*10;

    while(ll(jump)!=0){
		//cout<<a<<" "<<b<<endl;
        vi dirA = {1,0,-1,-1,-1,0,1,1,0};
        vi dirB = {-1,-1,-1,0,1,1,1,0,0};

        //if(k==1) rep(i,0,8) dirB[i] = 0;

        ll bestDir = -1;
        ll best = 1e18;

        rep(i,0,9){
            ll curr = getCost({a+dirA[i]*ll(jump),b+dirB[i]*ll(jump)});
            if(curr<best){
                bestDir = i;
                best = curr;
            }
        }

        a += dirA[bestDir]*ll(jump);
        b += dirB[bestDir]*ll(jump);

        jump*=0.9;
    }
    cout<<ans+getCost({a,b})<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'll getCost(vi)':
bridge.cpp:23:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(bridges[j]<0||bridges[j]>=points.size()) return 1e18;

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