fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define haisondeptraivippro signed
  4. #define fi first
  5. #define se second
  6. #define int long long
  7. #define ii pair<int ,int>
  8. #define mp make_pair
  9. map<int,int>d;
  10. int j=0,n,b[100068],m,s[100068];
  11. struct pt{
  12.     int d,c;
  13. };
  14. pt a[100068];
  15. bool cmp(pt x,pt y){
  16.     return x.d<y.d;
  17. }
  18.  haisondeptraivippro main()
  19. {
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(0);
  22.     cout.tie(0);
  23.     cin>>n>>m;
  24.     int ans=0;
  25.     for(int i=1;i<=m;i++){
  26.         cin>>a[i].d>>a[i].c;
  27.     }
  28.     sort(a+1,a+m+1,cmp);
  29.     for(int i=1;i<=m;i++){
  30.         b[i]=a[i].d;
  31.         s[i]=s[i-1]+a[i].d;
  32.        // cout<<a[i].d<<" "<<a[i].c<<'\n';        
  33.     }
  34.     for(int i=1;i<=m;i++){
  35.         int t=lower_bound(b+1,b+m+1,a[i].c)-b;
  36.         if(t<=m){
  37.             if(m-t+1>n)
  38.                 t=m-n+1;
  39.             int check=0,kt=0;
  40.             if(t<=i){
  41.                 check=a[t-1].d;
  42.                 kt=a[i].d;
  43.             }
  44.             int p=a[i].d+s[m]-s[t-1]+(n-(m-t+1)-(kt==0))*a[i].c-kt;
  45.          //   cout<<p<<" ";
  46.             if(check>0){
  47.                 p+=check;
  48.                 p-=a[i].d;
  49.             }
  50.          //  cout<<t<<" "<<p<<" "<<check<<'\n';
  51.         ans=max(ans,max(p,a[i].d+(n-1)*a[i].c));
  52.     }
  53.     else
  54.         ans=max(ans,a[i].d+(n-1)*a[i].c);
  55.     }
  56.     cout<<ans;
  57. }
  58.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uqEREd
language:
C++14 (clang 8.0)
created:
1 year 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!