fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // Function to calculate total points based on customer data and adTimes
  7. int calculatePoints(vector<int>& adTimes, const vector<pair<int, int>>& ads, const vector<pair<int, int>>& customers) {
  8.     int totalPoints = 0;
  9.  
  10.     for (auto customer : customers) {
  11.         int arrival = customer.first;
  12.         int duration = customer.second;
  13.  
  14.         int maxPoints = 0;
  15.         for (int i = 0; i < adTimes.size(); i++) {
  16.             int adStart = adTimes[i];
  17.             int adDuration = ads[i].first;
  18.             int adPoints = ads[i].second;
  19.  
  20.             // Check if the customer can fully watch the ad
  21.             if (adStart >= arrival && adStart + adDuration <= arrival + duration) {
  22.                 maxPoints = max(maxPoints, adPoints);
  23.             }
  24.         }
  25.         totalPoints += maxPoints;
  26.     }
  27.  
  28.     return totalPoints;
  29. }
  30.  
  31. // Backtracking function to assign ads
  32. void assignAds(int adIndex, vector<int>& adTimes, vector<bool>& timeline, int maxTime, const vector<pair<int, int>>& ads, const vector<pair<int, int>>& customers, int& maxPoints) {
  33.     if (adIndex == ads.size()) { // All ads assigned
  34.         maxPoints = max(maxPoints, calculatePoints(adTimes, ads, customers));
  35.         return;
  36.     }
  37.  
  38.     int adDuration = ads[adIndex].first;
  39.  
  40.     for (int startTime = 1; startTime <= maxTime; ++startTime) {
  41.         bool canPlace = true;
  42.  
  43.         // Check if the ad can be placed without overlapping
  44.         for (int t = startTime; t < startTime + adDuration; ++t) {
  45.             if (t > maxTime || timeline[t]) {
  46.                 canPlace = false;
  47.                 break;
  48.             }
  49.         }
  50.  
  51.         if (canPlace) {
  52.             // Place the ad
  53.             adTimes[adIndex] = startTime;
  54.             for (int t = startTime; t < startTime + adDuration; ++t) {
  55.                 timeline[t] = true;
  56.             }
  57.  
  58.             // Recurse for the next ad
  59.             assignAds(adIndex + 1, adTimes, timeline, maxTime, ads, customers, maxPoints);
  60.  
  61.             // Backtrack
  62.             for (int t = startTime; t < startTime + adDuration; ++t) {
  63.                 timeline[t] = false;
  64.             }
  65.             adTimes[adIndex] = -1;
  66.         }
  67.     }
  68. }
  69.  
  70. int main() {
  71.     // Ads: {duration, points}
  72.     vector<pair<int, int>> ads = {{3, 6}, {2, 4}, {1, 3}};
  73.  
  74.     // Customers: {arrival time, duration}
  75.     vector<pair<int, int>> customers = {{1, 5}, {1, 3}, {2, 4}, {2, 2}};
  76.  
  77.     // Maximum time (from customers' durations)
  78.     int maxTime = 10;
  79.  
  80.     // Initialize variables
  81.     vector<int> adTimes(ads.size(), -1); // Start times for each ad
  82.     vector<bool> timeline(maxTime + 1, false); // Track occupied time slots
  83.     int maxPoints = 0;
  84.  
  85.     // Start backtracking
  86.     assignAds(0, adTimes, timeline, maxTime, ads, customers, maxPoints);
  87.  
  88.     // Output the result
  89.     cout << "Maximum Points: " << maxPoints << endl;
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum Points: 18
https://ideone.com/xFtXBx
language:
C++ (gcc 8.3)
created:
10 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!