Submission #724935

#	Time	Username	Problem	Language	Result	Execution time	Memory
724935		yeyso	Road Closures (APIO21_roads)	C++14	7 / 100	51 ms	8072 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {

    int n = N;
    vector<int> u = U;
    vector<int> v = V;
    vector<ll> w;
    for(int i = 0; i < W.size(); i ++){
        w.push_back(W[i]);
    }

    vector<ll> res(n, 0);
    // k = 0 
    for(int i = 0; i < w.size(); i ++){
        res[0] += w[i];
    }
    // k = 1;
    vector<ll> dp(n-1, 0);
    for(int i = 0; i < w.size(); i ++){
        if(i >= 1){
            if(i >= 2){
                dp[i] = max(dp[i-1], dp[i-2]+w[i]);
            } else {
                dp[i] = max(dp[i-1], w[i]);
            }
        } else {
            dp[i] = w[i];
        }
        
    }
    res[1] = res[0] - dp[dp.size() - 1];
    return res;
}
/*
g++ -std=gnu++17 -O2 -pipe -o roads grader.cpp roads.cpp

6
0 1 3
1 2 2
2 3 1
3 4 4
4 5 1
*/

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:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < W.size(); i ++){
      |                    ~~^~~~~~~~~~
roads.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~
roads.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 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