Submission #45018

#	Time	Username	Problem	Language	Result	Execution time	Memory
45018		RezwanArefin01	Palembang Bridges (APIO15_bridge)	C++17	8 / 100	49 ms	4136 KiB

bridge

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

vector<int> pos;
ll sum[100100]; 

ll get(int l, int r) {
	if(l > r) return 0;
	ll ret = sum[r];
	if(l) ret -= sum[l - 1];
	return ret;
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, k; scanf("%d %d", &k, &n); 
	ll pre = 0; 
	for(int i = 0; i < n; i++) {
		char p, q; int s, t;
		scanf(" %c %d %c %d", &p, &s, &q, &t);
		if(p == q) pre += abs(s - t); 
		else { 
			pos.push_back(s);
			pos.push_back(t); 
			pre++;
		}
	} 
	if(!pos.size()) {
		printf("%lld\n", pre); exit(0); 
	}

	sort(pos.begin(), pos.end()); 
	n = pos.size(); 
	sum[0] = pos[0];
	for(int i = 1; i < n; i++) 
		sum[i] = sum[i - 1] + pos[i]; 

	if(k == 1) {
		ll add = 1e18; 
		for(int i = 0; i < n; i++) {
			ll tot = 1ll * pos[i] * (i + 1) - get(0, i);
			tot += get(i + 1, n - 1) - 1ll * pos[i] * (n - i - 1);
			add = min(add, tot); 
		} printf("%lld\n", add + pre);
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int main(int, const char**)':
bridge.cpp:24:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k; scanf("%d %d", &k, &n); 
            ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &p, &s, &q, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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