Submission #444317

#	Time	Username	Problem	Language	Result	Execution time	Memory
444317		Kitonds	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	288 ms	14388 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define read(A) freopen((A + ".in").c_str(),"r",stdin) 
#define write(A) freopen((A + ".out").c_str(),"w",stdout) 
#define ll long long
#define pb push_back
#define ull unsigned long long
#define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef pair<int, int> ii;      
typedef vector<ii> vii;      
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef pair<int, ii> iii;
typedef vector<iii> viii;
const int DFS_WHITE = 0;
const int DFS_BLACK = 1;
const int INF = 1e9 + 5;
const int MAXN = 105 ;
const int MOD = 1e9 + 7;

void setIO(string filename = ""){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	if(filename.size() == 0)
		return;
	read(filename);
	write(filename);
}

struct person
{
	int s, e;
	person(int s_, int e_){
		this->s = s_, this->e = e_;
	}
	bool operator <(const person &y){
		return s + e < y.s + y.e;
	}
};

int n, k, m;
multiset<int> upper, lower;
int cur_low, cur_up;
 
void in(int val){
	int med = (!lower.empty()? *lower.rbegin(): INF);
	if (val > med){
		upper.insert(val);
		cur_up += val;
		if (upper.size() > lower.size() + 1){
			int tmp = *upper.begin();
			lower.insert(tmp);
			upper.erase(upper.find(tmp));
			cur_up -= tmp;
			cur_low += tmp;
		}
	}
	else{
		lower.insert(val);
		cur_low += val;
		if (lower.size() > upper.size() + 1){
			int tmp = *lower.rbegin();
			upper.insert(tmp);
			lower.erase(lower.find(tmp));
			cur_up += tmp;
			cur_low -= tmp;
		}
	}
}

void solve(){
	cin>>m>>n;
	vector<person> A;
	int same = 0;
	for (int i=0; i<n; i++){
		int a, b;
		char c, d;
		cin>>c>>a>>d>>b;
		if (c == d){
			same += abs(a - b);
		}
		else{
			A.pb({a, b});
		}
	}
//	cout<<"A";
	A.pb({0, 0});
	sort(all(A));
	vi pref(A.size(), 0);
	for (int i=1; i<A.size(); i++){
		in(A[i].s);
		in(A[i].e);		
		pref[i] = cur_up - cur_low;
//		cout<<cur_up<<" "<<cur_low<<" "<<*lower.rbegin()<<endl;
//		cout<<A[i].s<<" "<<A[i].e<<endl;
	}
	int ans = pref[A.size() - 1];
	if(m == 2){
		lower.clear();
		upper.clear();
		cur_low = cur_up = 0;
		for (int i=A.size()-1; i>0; i--){
			in(A[i].s);
			in(A[i].e);
			ans = min(ans, cur_up - cur_low + pref[i - 1]);
		}
	}
	cout<<ans + same + A.size() - 1;
}	
	
signed main() {
	setIO();
	int test = 1;
//	cin>>test;
	while(test--){
		solve();
		if (test)
			cout<<endl;
	}
}

Compilation message (stderr)

bridge.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
bridge.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
bridge.cpp: In function 'void solve()':
bridge.cpp:97:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<person>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i=1; i<A.size(); i++){
      |                ~^~~~~~~~~
bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:7:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define read(A) freopen((A + ".in").c_str(),"r",stdin)
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:33:2: note: in expansion of macro 'read'
   33 |  read(filename);
      |  ^~~~
bridge.cpp:8:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define write(A) freopen((A + ".out").c_str(),"w",stdout)
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:34:2: note: in expansion of macro 'write'
   34 |  write(filename);
      |  ^~~~~

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