제출 #547983

#제출 시각아이디문제언어결과실행 시간메모리
547983fcmalkcinSightseeing in Kyoto (JOI22_kyoto)C++17
100 / 100
738 ms29028 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" #define pb push_back #define F(i,a,b) for(ll i=a;i<=b;i++) const ll maxn=5e5+100; const ll base=300; const ll mod= 1e9+7 ; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); struct comp { bool operator() (const pair<pll,pll> &a,const pair<pll,pll> &b) const { auto p=a.ff; auto p1=b.ff; if (p.ff*p1.ss>p1.ff*p.ss) return true; if (p.ff*p1.ss<p1.ff*p.ss) return false; return (a.ss>b.ss); } }; set<ll> st[2]; ll a[maxn][2]; set<pair<pll,pll>,comp> stp; ll pos[maxn]; ll val[maxn][2]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n, m; cin>> n>> m; ll cnt=0; for (int i=1; i<=n; i++) { cin>> a[i][0]; st[0].insert(i); if (i>=2) stp.insert(make_pair(make_pair(a[i][0]-a[i-1][0],1),make_pair(i,0))); } for (int i=1; i<=m; i++) { cin>> a[i][1]; st[1].insert(i); if (i>=2) stp.insert(make_pair(make_pair(a[i][1]-a[i-1][1],1),make_pair(i,1))); } while (stp.size()) { auto it=stp.begin(); stp.erase(it); auto p=((*it).ss); ll t=p.ss; cnt++; val[p.ff][t]=cnt; st[t].erase(p.ff); auto it1=st[t].lower_bound(p.ff); if (it1!=st[t].end()) { ll posnxt=(*it1); ll posnw=p.ff; it1--; ll pospre=(*it1); stp.erase(make_pair(make_pair(a[posnxt][t]-a[posnw][t],posnxt-posnw),make_pair(posnxt,t))); stp.insert(make_pair(make_pair(a[posnxt][t]-a[pospre][t],posnxt-pospre),make_pair(posnxt,t))); } } ll x=n; ll y=m; ll ans=0; while (max(x,y)!=1) { if (x==1) { ans+=a[x][0]; y--; } else if (y==1) { ans+=a[y][1]; x--; } else { if (val[x][0]>val[y][1]) { ans+=a[x][0]; y--; } else { ans+=a[y][1]; x--; } } } cout <<ans<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

kyoto.cpp: In function 'int main()':
kyoto.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...