English

There exists a \(O(n + dp + cp)\) time and space complexity dynamic programming solution for this problem.

Consider an array arr of length \((n + dp + cp)\) where \(dp\) and \(cp\) are maximum values of \(dp_i\) and \(cp_i\). arr[x] holds the maximum possible coolness points at x provided that Yiit is able to pick up this soda can. Based on the value of arr[x], we can update the value of arr[x + dp_i] if arr[x] + \(d_i\) is greater than its current value. We can also do a similar refinement based on \(cp_i\) and \(c_i\).

By iteratively doing refinements we can tabulate the dynamic programming array, and finding the largest value on the array gives us the answer.

Turkish

Bu soru için \(O(n + dp + cp)\) zaman ve memory complexity'si olan bir dynamic programming çözümü vardır.

En yüksek \(dp_i\) ve \(cp_i\) değerleri için uzunluğu \((n + dp + cp)\) olan bir array'imiz olsun. arr[x] x numaralı gazozun yanındayken Yiit'in gazozu almasına engel olabilecek herhangi bir durum olmaması şartıyla o an sahip olabileceği en yüksek sosyal statü puanını gösteriyor. arr[x] ve \(d_i\)'nin değerleri toplamı eğer arr[x + dp_i]nin değerinden yüksek ise array'in bu elemanını iyileştirebiliriz. Benzer şekilde \(cp_i\) ve \(c_i\) değerlerini kullanarak da iyileştirme yapabiliriz.

Tabulation metoduyla iyileştirmeleri dynamic programming array'ine doldurup array'deki en yüksek değeri alarak cevabı bulmuş oluruz.

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second

const int md = (int) 1e9 + 7;
const int siz = 300005;

ll arr[siz], d[siz], dt[siz], c[siz], ct[siz];
ll n, res;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin>>n;
    for(int i=0;i<n;i++) cin>>d[i];
    for(int i=0;i<n;i++) cin>>dt[i];
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++) cin>>ct[i];

    for(int i=0;i<n;i++) {
        d[i] += c[i];
        ct[i]++;
        dt[i] += ct[i];
    }


    for(int i=0;i<n;i++){
        if(arr[i + dt[i]] < arr[i] + d[i]) arr[i + dt[i]] = arr[i] + d[i];
        if(arr[i + ct[i]] < arr[i] + c[i]) arr[i + ct[i]] = arr[i] + c[i];
        if(arr[i + 1] < arr[i]) arr[i + 1] = arr[i];
    }

    for(int i=0;i<siz;i++){
        if(arr[i] > res) res = arr[i];
    }

    cout << res;

}