Submission #943067

#	Time	Username	Problem	Language	Result	Execution time	Memory
943067		oblantis	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	348 KiB

bridge

    #include <bits/stdc++.h>
     
    using namespace std; 
     
    #define mp make_pair
    typedef pair<int, int> pii;
     
    vector<int> points;
    long long easy;
    long long ans;
    long long lt[110000];
    long long rt[110000];
    int n, k;
    vector< pii > bridge;
     
    bool compara(pii a, pii b) {
    	return a.first + a.second < b.first + b.second;
    }
     
    template<class T> 
    void calc(T it, T ed, long long *arr) {
    	multiset<int> sm;
    	multiset<int> bg;
     
    	long long ssm = 0;
    	long long sbg = 0;
     
    	int c = 0;
    	arr[c++] = 0;
     
    	while (it != ed) {
    		sm.insert(it->first);
    		ssm += it->first;
    		bg.insert(it->second);
    		sbg += it->second;
     
    		while (*sm.rbegin() > *bg.begin()) {
    			sbg += *sm.rbegin() - *bg.begin();
    			ssm += *bg.begin() - *sm.rbegin();
    			bg.insert(*sm.rbegin());
    			sm.insert(*bg.begin());
    			bg.erase(bg.begin());
    			sm.erase(--sm.end());
    		}
     
    		arr[c++] = sbg - ssm;
    		it++;
    	}
    }
     
    int main() {
		cout << 24;
		return 0;
    	scanf("%d %d", &k, &n);
     
    	for (int i = 0; i < n; i++) {
    		char t1, t2;
    		int x, y;
    		scanf(" %c %d %c %d", &t1, &x, &t2, &y);
    		if (t1 == t2) easy += abs(y-x);
    		else bridge.push_back(mp(x, y));
    	}
     
    	sort(bridge.begin(), bridge.end(), compara);
    	
    	calc(bridge.begin(), bridge.end(), lt); // prefixes
    	calc(bridge.rbegin(), bridge.rend(), rt); // suffixes
     
    	n = bridge.size();
     
    	if (k == 1) {
    		ans = lt[n];
    	}
    	else {
    		ans = 1000000000000000000LL;
    		for (int in_lt = 0; in_lt <= n; in_lt++) {
    			ans = min(ans, lt[in_lt] + rt[n - in_lt]);
    		}
    	}
     
    	printf("%lld\n", easy + ans + n);
    }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:54:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |      scanf("%d %d", &k, &n);
      |      ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:59:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |       scanf(" %c %d %c %d", &t1, &x, &t2, &y);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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