oj.uz

Submission #758437

# Submission time Handle Problem Language Result Execution time Memory
758437 2023-06-14T15:46:24 Z BentoOreo Fruits (NOI22_fruits) C++14
5 / 100
 111 ms 12180 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 980 KB Output is correct
4 Correct 52 ms 6260 KB Output is correct
5 Correct 111 ms 12180 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 9608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -