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.     int T;
  72.     cin >> T; // Number of test cases
  73.  
  74.     while (T--) {
  75.         int C; // Number of customers
  76.         cin >> C;
  77.  
  78.         // Input the ads' points and durations
  79.         vector<pair<int, int>> ads(3); // {duration, points}
  80.         for (int i = 0; i < 3; ++i) cin >> ads[i].first; // Points
  81.         for (int i = 0; i < 3; ++i) cin >> ads[i].second;  // Durations
  82.  
  83.         // Input the customers' data
  84.         vector<pair<int, int>> customers(C); // {arrival, duration}
  85.         for (int i = 0; i < C; ++i) cin >> customers[i].first >> customers[i].second;
  86.  
  87.         // Calculate maximum time (from customers' durations)
  88.         int maxTime = 0;
  89.         for (auto customer : customers) {
  90.             maxTime = max(maxTime, customer.first + customer.second);
  91.         }
  92.  
  93.         // Initialize variables
  94.         vector<int> adTimes(ads.size(), -1); // Start times for each ad
  95.         vector<bool> timeline(maxTime + 1, false); // Track occupied time slots
  96.         int maxPoints = 0;
  97.  
  98.         // Start backtracking
  99.         assignAds(0, adTimes, timeline, maxTime, ads, customers, maxPoints);
  100.  
  101.         // Output the result for this test case
  102.         cout << "Maximum Points: " << maxPoints << endl;
  103.     }
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
1
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
stdout
copy 
Maximum Points: 16
https://ideone.com/9uE9jB
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!