You are viewing a single comment's thread. Return to all comments →
Here is my very simple solution in c++;
#include <bits/stdc++.h> using namespace std; long maximumPeople(vector<long> p, vector<long> x, vector<long> y, vector<long> r) { vector<pair<long,long>> cl; vector<pair<long,long>> pl; int cn=y.size(); int tn=x.size(); for(int i=0;i<cn;i++) cl.push_back({y[i]-r[i],y[i]+r[i]}); for(int i=0;i<tn;i++) pl.push_back({x[i],p[i]}); sort(cl.begin(),cl.end()); sort(pl.begin(),pl.end()); vector<long> surrounded(cn,0); long already=0; long must=0; int nc=0; for(int town=0;town<tn;town++){ while(nc<cn && cl[nc].second<pl[town].first) nc++; if(nc>=cn) already+=pl[town].second; else if(cl[nc].first>pl[town].first) already+=pl[town].second; else{ int justnext=nc+1; while(justnext<cn && cl[justnext].second<pl[town].first) justnext++; if(justnext>=cn) surrounded[nc]+=pl[town].second; else if(cl[justnext].first>pl[town].first) surrounded[nc]+=pl[town].second; } } for(auto e:surrounded) must=max(must,e); return must+already; } int main() { int n,m; cin >> n; vector<long> p(n),x(n); for (int i = 0; i < n; i++)cin >> p[i]; for (int i = 0; i < n; i++)cin >> x[i]; cin >> m; vector<long>y(m),r(m); for (int i = 0; i < m; i++)cin >> y[i]; for (int i = 0; i < m; i++)cin >> r[i] ; long result = maximumPeople(p, x, y, r); cout << result; }
Seems like cookies are disabled on this browser, please enable them to open this website
Cloudy Day
You are viewing a single comment's thread. Return to all comments →
Here is my very simple solution in c++;