PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Yash Daga
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Your friend works as a valet where N cars show up in a shift. The i-th car will arrive T_i seconds after the current moment, and the car can wait for at most Y_i seconds. That is, your friend can only start parking the car from time T_i to T_i+Y_i (inclusive).
Additionally, it takes X_i time to park the i-th car, which means he cannot park any other cars for X_i seconds starting from the time he starts parking the i-th car. It is known that no driver would like to wait for more time than it takes to park his car, so that Y_i < X_i for all i. The driver of the i-th car will pay A_i coins as a tip to your friend if his car is parked. Note that he can start parking the next car immediately after he finishes parking the previous car.
Your friend has asked you what will be the maximum possible earnings if he optimally chooses which cars to park and at what times.
EXPLANATION:
The basic idea is to run Tmax^2 Dynamic Programming. But before applying Dynamic Programming we had to calculate Best[i][j].
Best[i][j] is defined as the maximum tip we can generate by starting parking of a car at a time i such that it takes j times to park that car. How can we calculate this Best[i][j] ?
To calculate Best[i][j], for each value of X, i.e. the time required to park the car (j in this array), we can do scanline sort of thing where we first insert the starting point and ending point for each tip, where X[i]=j, and use a map to store the currently available tips, and then take the best tip out of those.
The dimension of the Best table will be 8000*4000 instead of 4000*4000, as the maximum time we can start parking the car can be time[i]+y[i].
Pseudo Code
for(auto p:v[j])
{
seg.pb({tim[p], {1, a[p]}});
seg.pb({tim[p]+y[p]+1, {-1, a[p]}});
}
sort(seg.begin(), seg.end());
map <int, int> mp;
int lim=seg.size(), cur=0;
for(int i=1;i<N;i++)
{
while(cur<lim && seg[cur].ff==i)
{
int typ=seg[cur].ss.ff, val=seg[cur].ss.ss;
if(typ==1)
mp[val]++;
else
{
mp[val]--;
if(mp[val]==0)
mp.erase(val);
}
cur++;
}
if(mp.size())
{
auto it=mp.end();
it--;
best[i][j]=(*it).ff;
}
}
Now we move towards Dynamic Programming to find the maximum coins that we can earn. Our DP is defined as:
DP[I] denotes the maximum coins that we can earn we start from time I. What will be our transitions? It is a kind of knapsack.
Suppose we are at a time i, and we can park some car at this time, then one time we will decide to park this car and the next time we decide not to park this car. Hence we could easily find out the maximum coins that we can earn if we decide the carks to park optimally.
TIME COMPLEXITY:
O(NlogN + Tmax^2)
SOLUTION:
Setter
#include <bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define fill(a,b) memset(a, b, sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define int long long
using namespace std;
const long long N=8005, INF=2000000000000000000, N1=4005;
long long dp[N]; // dp[i] is the best answer possible if he starts from time i
int best[N][N1]; // best[i][j] is the most amout of tip he can get if he starts parking at time i and takes j seconds to park.
long long fun(int pos)
{
if(pos>=N)
return 0ll;
if(dp[pos]!=-1)
return dp[pos];
dp[pos]=0;
for(int i=1;i<N1;i++)
{
if(best[pos][i])
dp[pos]=max(dp[pos], 0ll+best[pos][i]+fun(pos+i));
}
dp[pos]=max(dp[pos], fun(pos+1));
return dp[pos];
}
int32_t main()
{
IOS;
int t=1;
//cin>>t;
while(t--)
{
int n;
cin>>n;
fill(best, 0);
fill(dp, -1);
int tim[n], x[n], y[n], a[n];
vector <int> v[N];
for(int i=0;i<n;i++)
cin>>tim[i];
for(int i=0;i<n;i++)
{
cin>>x[i];
v[x[i]].pb(i);
}
for(int i=0;i<n;i++)
cin>>y[i];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=1;i<N1;i++)
{
if(v[i].size()==0)
continue;
vector <pair <int, pair <int, int> > > seg;
for(auto p:v[i])
{
seg.pb({tim[p], {1, a[p]}});
seg.pb({tim[p]+y[p]+1, {-1, a[p]}});
}
sort(seg.begin(), seg.end());
map <int, int> mp;
int lim=seg.size(), cur=0;
for(int j=1;j<N;j++)
{
while(cur<lim && seg[cur].ff==j)
{
int typ=seg[cur].ss.ff, val=seg[cur].ss.ss;
if(typ==1)
mp[val]++;
else
{
mp[val]--;
if(mp[val]==0)
mp.erase(val);
}
cur++;
}
if(mp.size())
{
auto it=mp.end();
it--;
best[j][i]=(*it).ff;
}
}
}
cout<<fun(1)<<"\n";
}
}