top of page

CCC 2021 S3: Lunch Concert

Updated: Oct 23, 2021

This is a binary search problem.

Implement the algrithom:

  1. Compute mid-1, mid, mid+1, if P(mid-1)< P(mid)< p(mid+1), the result will be left side: left , mid-1

  2. if P(mid-1)> p(mid) > p(mid+1), the result will be rightside: mid+1, right.

  3. ifP(mid-1) >p(mid) and P(mid+1) > p(mid), mid is the point.



#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

#define pairlonglong pair<long long,pair<bool,long long>>

vector<pairlonglong> arr;

bool compare(pairlonglong a, pairlonglong b){
   if(a.first < b.first){
      return true;
   }
   return false;
}

int main(){
   int a;
   cin >> a;
   long long x,y,z;
   long long right = 0,ans = 0,left = 0;
   for(int i = 0;i < a;i++){
      cin >> x >> y >> z;
      arr.push_back(make_pair(max(0LL,x-z),make_pair(false,y)));
      arr.push_back(make_pair(x+z,make_pair(true,y)));
      ans += max(0LL,x-z)*y;
      right += y;
   }
   sort(arr.begin(),arr.end(),compare);

   arr.insert(arr.begin(),make_pair(0LL,make_pair(false,0LL)));

   long long temp = ans;

   for(int i = 1;i < arr.size();i++){
      while(i < arr.size() && arr[i-1].first == arr[i].first){
         if(arr[i].second.first == true){
            left += arr[i].second.second;
         }else{
            right -= arr[i].second.second;
         }
         i++;
      }
      temp += (left-right)*(arr[i].first-arr[i-1].first);
      ans = min(ans,temp);
      if(arr[i].second.first == true){
         left += arr[i].second.second;
      }else{
         right -= arr[i].second.second;
      }
   }

   cout << ans << endl;
}

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comentários


bottom of page