답안 #60627 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60627	2018-07-24T11:57:59 Z	istlemin	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1100 ms	4224 KB

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;
}

Compilation message

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.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	504 KB	Output is correct
5	Correct	9 ms	612 KB	Output is correct
6	Correct	6 ms	612 KB	Output is correct
7	Correct	9 ms	612 KB	Output is correct
8	Correct	7 ms	692 KB	Output is correct
9	Correct	9 ms	692 KB	Output is correct
10	Correct	6 ms	692 KB	Output is correct
11	Correct	8 ms	692 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	692 KB	Output is correct
2	Correct	3 ms	692 KB	Output is correct
3	Correct	5 ms	692 KB	Output is correct
4	Correct	7 ms	692 KB	Output is correct
5	Correct	9 ms	692 KB	Output is correct
6	Correct	7 ms	692 KB	Output is correct
7	Correct	6 ms	692 KB	Output is correct
8	Correct	6 ms	692 KB	Output is correct
9	Correct	10 ms	692 KB	Output is correct
10	Correct	7 ms	692 KB	Output is correct
11	Correct	9 ms	692 KB	Output is correct
12	Correct	486 ms	4044 KB	Output is correct
13	Correct	584 ms	4136 KB	Output is correct
14	Correct	507 ms	4136 KB	Output is correct
15	Correct	350 ms	4136 KB	Output is correct
16	Correct	456 ms	4136 KB	Output is correct
17	Correct	505 ms	4136 KB	Output is correct
18	Correct	664 ms	4176 KB	Output is correct
19	Correct	542 ms	4176 KB	Output is correct
20	Correct	543 ms	4176 KB	Output is correct
21	Correct	628 ms	4176 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4176 KB	Output is correct
2	Correct	2 ms	4176 KB	Output is correct
3	Correct	3 ms	4176 KB	Output is correct
4	Correct	3 ms	4176 KB	Output is correct
5	Correct	3 ms	4176 KB	Output is correct
6	Correct	3 ms	4176 KB	Output is correct
7	Correct	3 ms	4176 KB	Output is correct
8	Correct	2 ms	4176 KB	Output is correct
9	Correct	2 ms	4176 KB	Output is correct
10	Correct	3 ms	4176 KB	Output is correct
11	Correct	4 ms	4176 KB	Output is correct
12	Correct	2 ms	4176 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4176 KB	Output is correct
2	Correct	3 ms	4176 KB	Output is correct
3	Correct	3 ms	4176 KB	Output is correct
4	Correct	3 ms	4176 KB	Output is correct
5	Correct	3 ms	4176 KB	Output is correct
6	Correct	3 ms	4176 KB	Output is correct
7	Correct	3 ms	4176 KB	Output is correct
8	Correct	4 ms	4176 KB	Output is correct
9	Correct	3 ms	4176 KB	Output is correct
10	Correct	3 ms	4176 KB	Output is correct
11	Correct	1 ms	4176 KB	Output is correct
12	Correct	3 ms	4176 KB	Output is correct
13	Correct	8 ms	4176 KB	Output is correct
14	Correct	12 ms	4176 KB	Output is correct
15	Correct	14 ms	4176 KB	Output is correct
16	Correct	4 ms	4176 KB	Output is correct
17	Correct	4 ms	4176 KB	Output is correct
18	Correct	7 ms	4176 KB	Output is correct
19	Correct	8 ms	4176 KB	Output is correct
20	Correct	10 ms	4176 KB	Output is correct
21	Correct	7 ms	4176 KB	Output is correct
22	Correct	7 ms	4176 KB	Output is correct
23	Correct	8 ms	4176 KB	Output is correct
24	Correct	9 ms	4176 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4176 KB	Output is correct
2	Correct	3 ms	4176 KB	Output is correct
3	Correct	2 ms	4176 KB	Output is correct
4	Correct	4 ms	4176 KB	Output is correct
5	Correct	3 ms	4176 KB	Output is correct
6	Correct	2 ms	4176 KB	Output is correct
7	Correct	3 ms	4176 KB	Output is correct
8	Correct	3 ms	4176 KB	Output is correct
9	Correct	3 ms	4176 KB	Output is correct
10	Correct	2 ms	4176 KB	Output is correct
11	Correct	4 ms	4176 KB	Output is correct
12	Correct	5 ms	4176 KB	Output is correct
13	Correct	9 ms	4176 KB	Output is correct
14	Correct	10 ms	4176 KB	Output is correct
15	Correct	8 ms	4176 KB	Output is correct
16	Correct	4 ms	4176 KB	Output is correct
17	Correct	5 ms	4176 KB	Output is correct
18	Correct	5 ms	4176 KB	Output is correct
19	Correct	6 ms	4176 KB	Output is correct
20	Correct	9 ms	4176 KB	Output is correct
21	Correct	11 ms	4176 KB	Output is correct
22	Correct	9 ms	4176 KB	Output is correct
23	Correct	11 ms	4176 KB	Output is correct
24	Correct	9 ms	4176 KB	Output is correct
25	Correct	673 ms	4176 KB	Output is correct
26	Correct	951 ms	4176 KB	Output is correct
27	Correct	872 ms	4176 KB	Output is correct
28	Correct	979 ms	4176 KB	Output is correct
29	Correct	1100 ms	4224 KB	Output is correct
30	Correct	632 ms	4224 KB	Output is correct
31	Correct	560 ms	4224 KB	Output is correct
32	Correct	1032 ms	4224 KB	Output is correct
33	Correct	997 ms	4224 KB	Output is correct
34	Correct	756 ms	4224 KB	Output is correct
35	Correct	586 ms	4224 KB	Output is correct
36	Correct	775 ms	4224 KB	Output is correct
37	Correct	550 ms	4224 KB	Output is correct

답안 #60627

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0