oj.uz

Submission #60627

# Submission time Handle Problem Language Result Execution time Memory
60627 2018-07-24T11:57:59 Z istlemin Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1100 ms 4224 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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