156972025-02-21 19:41:09GervidZebra (75 pont)cpp17Wrong answer 0/751ms552 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<int> side(N), timeArr(N);
    for (int i = 0; i < N; i++){
        cin >> side[i];
    }
    for (int i = 0; i < N; i++){
        cin >> timeArr[i];
    }
    
    // Gyalogosok tárolása (érkezési idő, irány)
    vector<pair<ll,int>> pedestrians;
    for (int i = 0; i < N; i++){
        pedestrians.push_back({timeArr[i], side[i]});
    }
    // Rendezzük időrend szerint
    sort(pedestrians.begin(), pedestrians.end(), [](auto a, auto b){
        return a.first < b.first;
    });
    
    // Átmásoljuk 1-indexelt tömbbe a kényelmes hozzáférhetőségért
    vector<ll> t(N+1, 0);
    vector<int> s(N+1, 0);
    for (int i = 1; i <= N; i++){
        t[i] = pedestrians[i-1].first;
        s[i] = pedestrians[i-1].second;
    }
    
    // Prefixösszegek: időösszegek, illetve a két oldal számlálása
    vector<ll> prefix(N+1, 0);
    vector<int> count0(N+1, 0), count1(N+1, 0);
    for (int i = 1; i <= N; i++){
        prefix[i] = prefix[i-1] + t[i];
        count0[i] = count0[i-1] + (s[i] == 0);
        count1[i] = count1[i-1] + (s[i] == 1);
    }
    
    const ll INF = 1e18;
    vector<ll> dp(N+1, INF);
    dp[0] = 0;
    
    // DP: a j-edik gyalogosig (az időrendi sorban) számoljuk a minimális várakozást
    for (int j = 1; j <= N; j++){
        for (int i = 1; i <= j; i++){
            // A szegmens érvényességéhez legalább 1 darab 0-ás és 1-es oldalú gyalogos kell
            int zeros = count0[j] - count0[i-1];
            int ones  = count1[j] - count1[i-1];
            if (zeros >= 1 && ones >= 1){
                // Az átkelés optimális ideje: t[j] (a legutolsó érkezés)
                ll cost = (ll)(j - i + 1) * t[j] - (prefix[j] - prefix[i-1]);
                dp[j] = min(dp[j], dp[i-1] + cost);
            }
        }
    }
    
    cout << dp[N] << endl;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/75
1Accepted0/01ms316 KiB
2Wrong answer0/01ms316 KiB
3Wrong answer0/51ms316 KiB
4Wrong answer0/51ms316 KiB
5Wrong answer0/51ms316 KiB
6Wrong answer0/51ms316 KiB
7Wrong answer0/51ms316 KiB
8Wrong answer0/51ms316 KiB
9Wrong answer0/51ms316 KiB
10Wrong answer0/51ms316 KiB
11Wrong answer0/51ms552 KiB
12Wrong answer0/51ms532 KiB
13Wrong answer0/51ms316 KiB
14Wrong answer0/51ms316 KiB
15Wrong answer0/51ms328 KiB
16Wrong answer0/51ms404 KiB
17Wrong answer0/51ms316 KiB