Submission #185583

#	Time	Username	Problem	Language	Result	Execution time	Memory
185583		dndhk	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	78 ms	8544 KiB

bridge

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;
int N, K;
ll ans = 0;

vector<pll> vt;
vector<pll> v;

void solve1(){
	ll sidx = 0, scnt = 0;
	for(int i=0; i<vt.size(); i++){
		v.pb({vt[i].first, 1});
		v.pb({vt[i].second, -1});
		sidx+=vt[i].first;
		scnt--;
	}
	sort(v.begin(), v.end());
	ll sum = -1;
	for(int i=0; i<v.size(); i++){
		//cout<<v[i].first<<" "<<2LL * (sidx+scnt*v[i].first)+ans<<endl;
		if(sum==-1 || sum>sidx+scnt*v[i].first){
			sum = sidx + scnt*v[i].first;
		}
		if(v[i].second==1){
			sidx-=v[i].first;
			scnt++;
		}else{
			scnt++;
			sidx-=v[i].first;
		}
	}
	if(sum!=-1)	ans += 2LL * sum;
}

int main(){
	scanf("%d%d", &K, &N);
	for(int i=0; i<N; i++){
		getchar();
		char c1, c2; 
		int a, b;
		scanf("%c %d %c %d", &c1, &a, &c2, &b);
		if(c1==c2){
			ans+=(ll)(max(a, b) - min(a, b));
		}else{
			ans += (ll)(max(a, b) - min(a, b) + 1);
			vt.pb({(ll)min(a, b), (ll)max(a, b)});
		}
	}
	if(K==1){
		solve1();
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
bridge.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &N);
  ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %d %c %d", &c1, &a, &c2, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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