Submission #25069

#	Time	Username	Problem	Language	Result	Execution time	Memory
25069		kajebiii	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	123 ms	7596 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

struct PT {
	int x, y;
	PT() {}
	PT(int xx, int yy) : x(xx), y(yy) {}
	bool operator<(const PT &o) const{return x+y < o.x+o.y;}
};
struct SOL {
	priority_queue<int> m; //minus slope
	priority_queue<int, vector<int>, greater<int> > p; //plus slope;
	ll ans;
	SOL() : ans(0) {}
	void add(int l, int r) {
		m.push(l); p.push(r);
//		printf("%d %d add\n", l, r);
		while(true) {
			int mm = m.top();
			int pp = p.top(); 
			if(mm <= pp) return;
			p.pop(); m.pop();
			ans += abs(pp - mm);
			m.push(pp); p.push(mm);
//			printf("%d %d pop\n", mm, pp);
//			printf("%d %d push\n", pp, mm);
		}
	}
};

const int MAX_N = 1e5 + 100;

int K, N;
ll Ans = 0;
vector<PT> Ps;
ll DyL[MAX_N], DyR[MAX_N];
int main() {
	cin >> K >> N;
	REP(i, N) {
		char sa[3], sb[3]; int x, y;
		scanf("%s%d%s%d", sa, &x, sb, &y);
		if(sa[0] != sb[0]) {
			Ans += 1;
			Ps.push_back(PT(min(x, y), max(x, y)));
		}
		Ans += abs(x-y);
	}
	sort(ALL(Ps));

	if(K == 1) {
		SOL sol;
		for(PT &p : Ps) sol.add(p.x, p.y);
		Ans += sol.ans * 2;
		printf("%lld\n", Ans);
	} else {
		SOL lsol, rsol;
		for(int i=0; i<SZ(Ps); i++) {
			PT &p = Ps[i];
			lsol.add(p.x, p.y);
			DyL[i+1] = lsol.ans * 2;
		}
		for(int i=SZ(Ps)-1; i>=0; i--) {
			PT &p = Ps[i];
			rsol.add(p.x, p.y);
			DyR[i+1] = rsol.ans * 2;
		}

		ll nowAns = LINF;
		for(int i=0; i<=SZ(Ps); i++)
			nowAns = min(nowAns, DyL[i] + DyR[i+1]);
		Ans += nowAns;
		printf("%lld\n", Ans);
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:53:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", sa, &x, sb, &y);
                                    ^

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