Submission #1215272

#TimeUsernameProblemLanguageResultExecution timeMemory
1215272Madhav_1608Palembang Bridges (APIO15_bridge)C++20
100 / 100
44 ms9864 KiB
#include <iostream> #include <stack> #include <queue> #include <string> #include <algorithm> #include <vector> #include <map> #include <set> #include <climits> #include <cmath> #include <unordered_map> #include <unordered_set> #include <numeric> #include <iomanip> #include <cstring> #include <stdio.h> #include <assert.h> #include <complex> #include <array> #include <utility> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<string> vs; typedef vector<long long> vll; typedef pair<ll,ll> pll; #define double long double #define F first #define S second const double eps = 1e-12; #define FOR(i,a,b) for(long long i=a;i<b;i++) #define all(v) v.begin(),v.end() template <typename I> void print(vector<I> &v){ FOR(i,0,v.size()){cout << v[i] << " ";} cout << "\n"; } ll gcd(ll a,ll b){ if(a==0){return b;} else if(b==0){return a;} else if(a<b){return gcd(b%a,a);} else{return gcd(a%b,b);} } ll lcm(ll a,ll b){ return (a/gcd(a,b))*b; } void setIO(string name = "") { freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output freopen((name + ".out").c_str(), "w", stdout); } void init_code(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } vll cost(ll n,vll &a,vll &b){ priority_queue<ll> left; // including median priority_queue<ll,vll,greater<ll>> right; // excluding median ll suml = 0; ll sumr = 0; vll ans; if(a[0]<=b[0]) swap(a[0],b[0]); left.push(b[0]); right.push(a[0]); sumr += a[0]; suml += b[0]; ans.push_back(0); FOR(i,1,n){ ll med = left.top(); ans.push_back(sumr-suml); if(a[i]>med){ if(b[i]>med){ right.push(a[i]); right.push(b[i]); sumr += (a[i]+b[i]); left.push(right.top()); suml += right.top(); sumr -= right.top(); right.pop(); } else{ right.push(a[i]); sumr += a[i]; left.push(b[i]); suml += b[i]; } } else{ if(b[i]<=med){ left.push(a[i]); left.push(b[i]); suml += (a[i]+b[i]); right.push(left.top()); sumr += left.top(); suml -= left.top(); left.pop(); } else{ right.push(b[i]); sumr += b[i]; left.push(a[i]); suml += a[i]; } } } ans.push_back(sumr-suml); return ans; } void solve(){ // store very big numbers may mean log2. // A comparator must return false for two equal objects. Not doing so results in undefined behavior. ll k,n; cin >> k >> n; vll a; vll b; ll ans = 0; FOR(i,0,n){ char p,q; ll s,t; cin >> p >> s >> q >> t; if(p==q){ ans += abs(s-t); } else{ a.push_back(s); b.push_back(t); } } n = a.size(); if(n==0){ cout << ans << "\n"; return; } if(k==1){ vll left = cost(n,a,b); cout << (ans+left[n]+n) << "\n"; } else{ vector<pll> c; FOR(i,0,n){ c.push_back({a[i]+b[i],i}); } sort(all(c)); vll a1; vll b1; FOR(i,0,n){ a1.push_back(a[c[i].S]); b1.push_back(b[c[i].S]); } vll left = cost(n,a1,b1); reverse(all(a1)); reverse(all(b1)); vll right = cost(n,a1,b1); ll curr_ans = 1e16; FOR(i,0,n+1){ curr_ans = min(curr_ans,left[i]+right[n-i]); } cout << (ans+curr_ans+n) << "\n"; } } signed main(){ //setIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // init_code(); ll t=1; // cin >> t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'void init_code()':
bridge.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...