Submission #1147415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147415		Pacybwoah	Fruits (NOI22_fruits)	C++20	5 / 100	1094 ms	18592 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inf = 1e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> vec(n + 1), poss, prea(n + 1), used, visc(n + 1);
    vector<ll> cost(n + 1), prep;
    used.push_back(0);
    for(int i = 1; i <= n; i++) cin >> vec[i];
    for(int i = 1; i <= n; i++) cin >> cost[i];
    for(int i = 1; i <= n; i++) prea[i] = 1;
    int sz = 0, szz = 0, maxnow = 0;
    for(int i = 1; i <= n; i++){
        if(vec[i] > 0){
            prea[i] = 0;
            visc[vec[i]] = 1;
            if(maxnow < vec[i]){
                maxnow = vec[i];
                sz++;
                used.push_back(i);
            }
        }
    }
    poss.push_back(-1);
    prep.push_back(0);
    for(int i = 1; i <= n; i++){
        if(!visc[i]){
            poss.push_back(i);
            prep.push_back(prep.back() + cost[i]);
            szz++;
        }
        prea[i] += prea[i - 1];
    }
    vector<ll> dp(sz + 1);
    for(int i = 1; i <= sz; i++){
        for(int j = 0; j < i; j++){
            int ri = used[i], rj = used[j];
            int blk = prea[ri] - prea[rj];
            ll cal = 0;
            int canl = lower_bound(poss.begin(), poss.end(), vec[rj]) - poss.begin() - 1;
            int canr = lower_bound(poss.begin(), poss.end(), vec[ri]) - poss.begin() - 1;
            if(canr - canl > blk) cal = prep[canr] - prep[canr - blk];
            else cal = prep[canr] - prep[canl];
            dp[i] = max(dp[i], dp[j] + cal + cost[vec[ri]]);
        }
    }
    for(int i = 1; i <= n; i++){
        ll ans = 0;
        for(int j = 0; j <= sz; j++){
            if(used[j] > i) break;
            int rj = used[j];
            int blk = prea[i] - prea[rj];
            ll cal = 0;
            int canl = lower_bound(poss.begin(), poss.end(), vec[rj]) - poss.begin() - 1;
            int canr = lower_bound(poss.begin(), poss.end(), n + 1) - poss.begin() - 1;
            if(canr - canl > blk) cal = prep[canr] - prep[canr - blk];
            else cal = prep[canr] - prep[canl];
            ans = max(ans, dp[j] + cal);
        }
        cout << ans << " \n"[i == n];
    }
}
// g++ -std=c++20 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pE.cpp

• Subtask 1: 0 / 6
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 13
• Subtask 5: 0 / 23
• Subtask 6: 0 / 42