제출 #660011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660011		aebov	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	340 KiB

bridge

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<iomanip>
    #include<map>
    #include<utility>
    #include<unordered_map>
    #include<vector>
    #include<set>
    #define pii pair<int,int>
    #define F first
    #define S second
    #define ll long long
    #define pb push_back
    using namespace std;
     
    const int N = (int)1e5 + 5, mod = (ll)1e9 + 7;
    int n, k, x, y;
    char ch, hc;
    ll sm = 0, sm2 = (ll)1e9 + 18;
     
    void sub(){
    //	cerr << "\n entered #sub 2 \n";
    	vector<int> cv;
    	vector<pii> vc; vc.pb({0,0});
    	for(int i = 1; i <= n; i ++){
    		cin >> ch >> x >> hc >> y;
    		if(x < y)swap(x, y);
    		if(ch == hc) sm += x - y;
    		else vc.pb({y, x});
    	} n = vc.size() - 1;
    //	cout << "N " << n << endl;
    	for(int i = 1; i <= n; i ++) {
    		cv.pb(vc[i].F);
    		cv.pb(vc[i].S);
    	}
    	sort(cv.begin(), cv.end());
    //	for(auto u : cv)cout << u << endl;
    	for(int i = 0; i < (int)cv.size(); i ++){
    		for(int j = i; j < (int)cv.size(); j ++) {
    			int x = cv[i], y = cv[j];
    			ll sum = 0;
    			for(int z = 1; z < n; z ++){
    				if(vc[z].S < x) sum +=  (x<<1) - vc[z].F - vc[z].S + 1;
    				else if(vc[z].F > y) sum += vc[z].F + vc[z].S - (y<<1) + 1;
    				else if(x < vc[z].F && vc[z].S < y)sum += min(vc[z].F + vc[z].S -(x<<1) + 1,(y<<1) - vc[z].F - vc[z].S + 1);
    				else sum += vc[z].S - vc[z].F + 1;
    			}
    			sm2 = min(sm2, sum);
    		}
    	}
    //	cout << sm  << " " << sm2 << endl;
    	cout << sm + sm2 << endl;
    	exit(0);
    }
    int main(){
    	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    	cin >> k >> n;
    	vector<int> vc;
    	if(k == 2 && n < 101)sub();
    //	cerr << "\n enteres #sub1 \n";
    	for(int i = 1; i <= n; i ++){
    		cin >> ch >> x >> hc >> y;
    		if(ch == hc) sm += abs(x - y);
    		else sm ++, vc.pb(x), vc.pb(y);
    	}
    	sort(vc.begin(), vc.end());
    	int pos = vc[(vc.size() - 1) / 2];
    	for(auto x : vc)sm += abs(x - pos);
    	cout << sm << endl;
    }

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