Submission #15671

#	Time	Username	Problem	Language	Result	Execution time	Memory
15671		cki86201	Palembang Bridges (APIO15_bridge)	C++98	100 / 100	393 ms	12892 KiB

bridge

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<set>
using namespace std;

typedef long long ll;
int k, n, np;
ll ans;
struct Pair{
	Pair(){}
	Pair(int x, int y) :x(x), y(y){}
	int x, y;
	bool operator<(const Pair &l)const{
		return x + y < l.x + l.y;
	}
}p[100010];
ll dp[2][100010];

multiset <int> S;
multiset <int>::iterator it, jt;

void Do(int t){
	S.clear();
	S.insert(p[0].x), S.insert(p[0].y);
	it = S.begin();
	dp[t][0] = abs(p[0].x - p[0].y);
	for (int i = 1; i < np; i++){
		int cnt = (*it <= p[i].x) + (*it <= p[i].y);
		int delta = abs(*it - p[i].x) + abs(*it - p[i].y);
		S.insert(p[i].x), S.insert(p[i].y);
		if (cnt == 0)jt = it--;
		else if (cnt == 2){
			jt = it++;
			delta -= 2 * (*it - *jt);
		}
		dp[t][i] = dp[t][i - 1] + delta;
	}
}

int main(){
	scanf("%d%d", &k, &n);
	for (int i = 0; i < n; i++){
		char a[2], b[2];
		int c, d;
		scanf("%s%d%s%d", a, &c, b, &d);
		if (a[0] == b[0])ans += abs(c - d);
		else p[np++] = Pair(c, d);
	}
	sort(p, p + np);
	Do(0);
	if (k == 1)printf("%lld", np + ans + dp[0][np - 1]);
	else{
		reverse(p, p + np);
		Do(1);
		ll mn = min(dp[1][np - 1], dp[0][np - 1]);
		for (int i = 0; i < np - 1; i++){
			mn = min(mn, dp[0][i] + dp[1][np - i - 2]);
		}
		printf("%lld", mn + ans + np);
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:43:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^
bridge.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", a, &c, b, &d);
                                  ^

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