POI, C++ (gcc) - rextester

POI

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;

//https://www.youtube.com/watch?v=rF13507mRp8&t=237s
ll bestScore(const vector<int> &movies,const vector<ll> &score){
    const int n = movies.size();
    const int m = score.size();
    
    int  l = 0;//last movie viewed
    int  r = 0;//current movie to view
    vector<int> cnt(m);
    int movie_counter = 0;
    ll ans = 0;
    ll sum = 0;
    while(r  < n){
        const int &mid = movies[r];
        int &occ = ++cnt[mid];
        if(occ == 1){
            sum += score[mid];
            ++movie_counter;
        }
        else if(occ == 2)
        {
            sum -= score[mid];
        }
        else if(movie_counter == m){
            while(movie_counter == m){
                //keep removing left most watched movies till the counter becomes 0 for some movie from the left
                const int  &watch_counter = --cnt[movies[l]];
                const int &scr = score[movies[l++]];
                if(watch_counter == 1)//if watch counter reduces to one then add the score of that movie from sum
                {
                    sum += scr;
                }
                else if(watch_counter == 0)//if watch counter reduces to 0 then reduce the score of that movie from sum
                {
                    sum -= scr;
                    --movie_counter;
                     break;
                }
            }
            
        }
        // cout<<l<<" : "<<r<<" = "<<sum<<"\n";
        ans = max(ans,sum);
        ++r;
    }
    
    while(l < n){
         //cout<<l<<" : "<<r<<" = "<<sum<<"\n";
        const int &watch_counter = --cnt[movies[l]];
        const int &scr = score[movies[l++]];
        if(watch_counter == 1)
            sum += scr;
        else if(watch_counter == 0){
            sum -= scr;
        }
        ans = max(ans,sum);
    }
    
    return ans;
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> movie(n);
    vector<ll> score(m);
    
    for(int &x : movie)
    {
        cin >> x;
        x--;
    }
    for(ll  &y : score)
        cin >> y;
    
    cout << bestScore(movie,score) <<"\n";
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development