이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define float long double
#define pff pair<float,float>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(),v.end()
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define forn(i,st,n,inc) for(int i=st;i<n;i+=inc)
#define rforn(i,st,n,inc) for(int i=st-1;i>=n;i-=inc)
#define bruh cout<<"\nbruh\n"; exit(0);
#define UB(v,x) upper_bound(all(v),x)
#define LB(v,x) lower_bound(all(v),x)
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pi acos(-1)
const int MOD = 1e9+7;
const int64_t INF64 = INT64_MAX;
const int32_t INF32 = INT32_MAX;
ostream& operator<<(ostream& o,const string& s){
for(auto c:s) o<<c;
return o;
}
template<typename F,typename S>
ostream& operator<<(ostream& o,const pair<F,S>& p){
o<<"["<<p.fi<<","<<p.se<<"]";
return o;
}
template<typename... T,template<class...> class C>
ostream& operator<<(ostream& o,const C<T...>& v){
o<<"[";
int tot=0;
for(auto x:v){
o<<x;
if(tot<v.size()-1) o<<",";
tot++;
}
o<<"]";
return o;
}
vector<string> vec_splitter(string s) {
s += ',';
vector<string> res;
while(!s.empty()) {
res.push_back(s.substr(0, s.find(',')));
s = s.substr(s.find(',') + 1);
}
return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx,
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
stringstream ss; ss << H;
cerr << args[idx] << " = " << ss.str();
debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef OFFLINE
clock_t Tm=clock();
#define debug(...) //debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...)
#endif
void init(){
}
void solve(){
int k,n;
cin>>k>>n;
ll ans=0;
vector<ll> P={0},Q={0};
for(int i=0;i<n;i++){
char a,b;
ll x,y;
cin>>a>>x>>b>>y;
if(a==b) ans+=abs(x-y);
else{
if(a=='B'){
swap(a,b);
swap(x,y);
}
P.pb(x);
Q.pb(y);
}
}
sort(all(P));
sort(all(Q));
int m=size(P)-1;
vector<ll> PP(m+1),QP(m+1);
for(int i=1;i<=m;i++){
PP[i]=PP[i-1]+P[i];
QP[i]=QP[i-1]+Q[i];
}
debug(P,PP);
debug(Q,QP);
ans+=PP[m]+QP[m]+m;
debug(m,ans);
ll X,res=0,now;
int lp,lq;
for(int i=1;i<=m;i++){
// zone A
X = P[i];
lp = i, lq = UB(Q,X) - begin(Q) -1;
now = 2* (X*(lp+lq-m) - PP[lp] - QP[lq]);
res = min(res , now);
debug(now,ans+now,lp,lq);
// zone B
X = Q[i];
lq = i, lp = UB(P,X) - begin(P) -1;
now = 2* (X*(lp+lq-m) - PP[lp] - QP[lq]);
res = min(res , now);
debug(now,ans+now,lp,lq);
}
cout<<ans+res;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie();
//If you hack my code , You are gay
init();
int T=1;
//cin>>T;
//scanf("%d",&T);
while(T--){
solve();
//cout<<"\n";
//printf("\n");
}
//mara kha
#ifdef OFFLINE
//cerr<<"Time = "<<(double)(clock()-Tm)/CLOCKS_PER_SEC;
#endif
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |