Submission #981637

#	Time	Username	Problem	Language	Result	Execution time	Memory
981637		Ghulam_Junaid	Road Closures (APIO21_roads)	C++17	12 / 100	40 ms	4956 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"

using namespace std;

typedef long long ll;

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    int n = N;
    vector<ll> ans(n, 0);
    bool subtask1 = 1, subtask2 = 1;
    for (int i = 0; i < n - 1; i ++){
        subtask1 &= (U[i] == 0);
        subtask2 &= (U[i] == i and V[i] == i + 1);
    }

    ll sm = 0;
    for (int i = 0; i < n - 1; i ++)
        sm += W[i];
    ans[0] = sm;
    if (subtask1){
        sort(W.begin(), W.end());    
        for (int i = 1; i < n; i ++)
            ans[i] = ans[i - 1] - W[n - i - 1];
    }
    if (subtask2){
        ll dp[n][2];
        dp[0][0] = W[0];
        dp[0][1] = 0;

        for (int i = 1; i < W.size(); i ++){
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + W[i];
            dp[i][1] = dp[i - 1][0];
        }
        ans[1] = min(dp[W.size() - 1][0], dp[W.size() - 1][1]);
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i = 1; i < W.size(); i ++){
      |                         ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22