fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 200005;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. struct item{
  41.         int a, b;
  42.         item(int a = 0, int b = 0) :
  43.                 a(a), b(b) {}
  44.  
  45.         bool operator < (const item & o) const{
  46.                 return b == o.b ? a < o.a : b < o.b;
  47.         }
  48.  
  49.         void input(void){
  50.                 cin >> a >> b;
  51.         }
  52. }vil[MAXN];
  53.  
  54. int n;
  55.  
  56. struct line{
  57.         ll a, b;
  58.         line(ll a = 0, ll b = 0) :
  59.                 a(a), b(b) {}
  60.  
  61.         ll cost(ll x){
  62.                 return a * x + b;
  63.         }
  64.  
  65.         bool check(line l, line r){
  66.                 return (b - l.b) * (l.a - r.a) <= (r.b - l.b) * (l.a - a);
  67.         }
  68. };
  69. deque <line> D;
  70.  
  71. ll get(ll x){
  72.         while(SZ(D) > 1 && D[0].cost(x) <= D[1].cost(x))
  73.                     D.pop_front();
  74.         return D[0].cost(x);
  75. }
  76.  
  77. void add(line val){
  78.         while(SZ(D) > 1 && val.check(D[SZ(D) - 2], D.back()))
  79.                 D.pop_back();
  80.         D.PB(val);
  81. }
  82.  
  83. void check(void){
  84.         FOR(i, 1, n) if(vil[i].a != vil[i].b) return;
  85.  
  86.         ll res = 0;
  87.         add(line());
  88.         FOR(i, 1, n){
  89.                 maximize(res, 1ll * vil[i].a * (n - i + 1) + get(i));
  90.                 add(line(vil[i].b, - 1ll * vil[i].b * i));
  91.         }
  92.         cout << res;
  93.         exit(0);
  94. }
  95.  
  96. void solve(void){
  97.         cin >> n;
  98.         FOR(i, 1, n) vil[i].input();
  99.         sort(vil + 1, vil + n + 1);
  100. //        FOR(i, 1, n) cout << vil[i].b << " " << vil[i].a << "\n";
  101.         if(vil[n].b == 0){
  102.                 ll res = 0;
  103.                 FOR(i, 1, n) maximize(res, 1ll * vil[i].a * (n - i + 1));
  104.                 return void(cout << res);
  105.         }
  106.  
  107.         check();
  108.  
  109.         if(n <= 300){
  110.                 ll res = 0;
  111.                 FOR(i, 1, n) FOR(j, 1, n){
  112.                         if(vil[i].a >= vil[j].b){
  113.                                 ll sum = 0;
  114.                                 FOR(k, 1, n){
  115.                                         if(vil[k].a >= vil[i].a) sum += vil[i].a;
  116.                                         else if(vil[k].b >= vil[j].b) sum += vil[j].b;
  117.                                 }
  118.                                 maximize(res, sum);
  119.                         }
  120.                 }
  121.                 return void(cout << res);
  122.         }
  123.  
  124.  
  125. }
  126.  
  127. int main(void){
  128.  
  129.         ios_base :: sync_with_stdio(0);
  130.         cin.tie(0); cout.tie(0);
  131.  
  132.         #define TaZinh "test"
  133.  
  134.         if(fopen(TaZinh".inp", "r"))
  135.                 TSun(TaZinh);
  136.  
  137.         int Sun = 1;
  138. //        cin >> Sun;
  139.         REP(love, Sun) solve();
  140.  
  141.         return 0;
  142. }
  143.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mqN8vB
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!