제출 #758437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758437		BentoOreo	Fruits (NOI22_fruits)	C++14	5 / 100	111 ms	12180 KiB

Main

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <deque>
#include <set>
#include <unordered_set>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> station,fruit;
    ll x;
    ll negcount = 0;
    vector<ll> locked;
    for(int i = 0; i < n; i++){
        cin >> x;
        if(x == -1){
            negcount++;
        }
        station.push_back(x);
    }
    for(int i = 0; i < n; i++){
        cin >> x;
        fruit.push_back(x);
    }
    if(negcount == n){
        ll sum = 0;
        char c = ' ';
        sort(fruit.rbegin(),fruit.rend());
        for(int i = 0; i < n; i++){
            sum += fruit.at(i);
            if(i == n-1){
                c = '\n';
            }
            cout << sum << c;
        }
    } else if (n <= 200){
        //post processing
        
        vector<pair<ll,ll> > moveable;//moveable fruits, tastiness:cost kv pair
        unordered_map<ll,pair<ll,ll> > immovable; //immovable fruits {station} : pair <tastiness, cost>
        for(int i = 0; i < n; i++){
            if(station.at(i) != -1){
                immovable[i+1] = {station.at(i),fruit.at(i)};
                fruit.at(station.at(i)-1) = -1;
            }
        }
        for(int i = 0; i < n; i++){
            if(fruit.at(i) != -1){
                moveable.push_back({i+1,fruit.at(i)});
            }
        }
        vector<ll> maxof(n,0);//max for each iteration, we will go through each permutation, check sums 1 to n
        // INCLUDE LOCKED fruits when necessary
        // max of each sum at i
        do{
            ll total_cost= 0;
            ll last_max = 0;
            int mv = 0;
            for(int i = 0; i < n; i++){
                if(immovable.count(i+1)){//it is here
                    if(immovable[i+1].first > last_max){
                        last_max = immovable[i+1].first;//careful about indexing here
                        total_cost += immovable[i+1].second;
                    }
                } else {
                    if(moveable.at(mv).first > last_max){
                        last_max = moveable.at(mv).first;
                        total_cost += moveable.at(mv).second;
                    }
                    mv++; //read other thing in array
                }
                maxof.at(i) = max(maxof.at(i),total_cost); // update for this array
            }
            /*
            Benson will onyl buy if tastiness is greater than my current tastiness level
            for i in range(n):
                if
            */ 
        } while(next_permutation(moveable.begin(),moveable.end()));
        int i = 0;
        char c = ' ';
        for(auto &num : maxof){
            if(i == n-1){
                c = '\n';
            }
            cout << num << c;
            i++;
        }
        
    }
}

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