Submission #745063

#	Time	Username	Problem	Language	Result	Execution time	Memory
745063		Nahian9696	Road Closures (APIO21_roads)	C++17	12 / 100	46 ms	6328 KiB

roads

#include "roads.h"

#include <iostream>
#include <iomanip>

#include <cmath>
#include <cstring>
#include <algorithm>


#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>

using namespace std;


typedef long double                         ld;
typedef long long                           ll;
typedef vector<int32_t>                     vi;
typedef vector<ll>                          vll;
typedef pair<int32_t, int32_t>              pii;



#define endl                                "\n"
#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}








std::vector<long long> 
minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    
    bool star = true;

    f0(i, N-1) {
        if(U[i] != 0) star = false;
    }

    if(star) {
        sort(all(W));
        vll ret(N, 0);
        ll sum = 0;
        f0(i, N-1) sum += W[i];
        f0(i, N) {
            ret[i] = sum;
            if(i != N-1)
            sum -= W[N-i-2];
        }
        return ret;
    }

    vll ret(N, 0);
    ll sum = 0;
    f0(i, N-1) sum += W[i];
    ret[0] = sum;

    if(N == 2) {
        ret[1] = W[0];
        return ret;
    }

    N--;

    ll dp[N];

    dp[0] = W[0];
    dp[1] = max(W[0], W[1]);

    for(int i = 2; i < N; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + W[i]);
    }

    ret[1] = sum - dp[N-1];


    return ret;
    return std::vector<long long>(N, 0);
}

• 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