Submission #588593

#	Time	Username	Problem	Language	Result	Execution time	Memory
588593		Jomnoi	Road Closures (APIO21_roads)	C++17	5 / 100	55 ms	3872 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

const int MAX_N = 1e5 + 5;

int dp[MAX_N];
bool used[MAX_N];

vector <long long> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W) {
    bool subtask1 = true, subtask2 = true;

    for(int i = 0; i < N - 1; i++) {
        if(U[i] != 0 and V[i] != 0) {
            subtask1 = false;
        }
        if(U[i] != i or V[i] != i + 1) {
            subtask2 = false;
        }
    }
    
    vector <long long> ans;
    if(subtask1 == true) {
        sort(W.rbegin(), W.rend());

        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }
        for(int i = 0; i < N - 1; i++) {
            ans.push_back(sum);
            sum -= W[i];
        }
        ans.push_back(0);
    }
    else if(subtask2 == true) {
        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }
        ans.push_back(sum);
        
        for(int i = 0; i < N - 1; i++) {
            dp[i] = W[i];
            if(i - 1 >= 0) {
                dp[i] = max(dp[i], dp[i - 1]);
            }
            if(i - 2 >= 0) {
                dp[i] = max(dp[i], dp[i - 2] + W[i]);
            }
        }
        ans.push_back(sum - dp[N - 2]);

        for(int i = 0; i < N - 2; i++) {
            ans.push_back(0);
        }
    }
    else if(N <= 200) {
        // do something
    }
    else if(N <= 2000) {
        // do something
    }
    return ans;
}

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