Submission #221801

#	Time	Username	Problem	Language	Result	Execution time	Memory
221801		patrikpavic2	Wiring (IOI17_wiring)	C++17	100 / 100	212 ms	62184 KiB

wiring

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  wiring
* score: 100.0
* date:  2019-06-13 11:05:56.973728
*/
//#include "wiring.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;

const int N = 3e5 + 500;
const int LOG = 18;
const ll INF = 1e18;
const int OFF = (1 << LOG);

ll prf[N];
map < int , ll > dp[N];
int n, L[N], R[N], G[N], rv[N];
vp v;

inline ll dis(int x,int y){
    return v[y].X - v[x].X;
}

inline ll get(int x,int y){
    if(x > y) return 0;
    return prf[y] - (x ? prf[x - 1] : 0);
}

ll f(int i,int lst){
    //printf("stanje %d %d G %d L %d R %d, rv %d\n", i, lst, G[i], L[i], R[i], rv[i]);
    if(dp[i][lst] != 0)
        return dp[i][lst] - 1;
    if(i == n){
        if(lst > 0 && i > 1)
            return -1 + (dp[i][lst] = f(i, lst - 1) + dis(L[i - 1] - 1, L[i] - lst) + 1);
        return -1 + (dp[i][lst] = (lst != 0) * INF + 1);
    }
    ll ret = INF;
    if(lst > 0)
        ret = min(ret, f(i, lst - 1) + dis(L[i] - lst, L[i]));
    if(lst <= G[i])
        ret = min(ret, f(i + 1, G[i] - lst) + get(L[i], L[i] + lst - 1) - get(L[i] - lst, L[i] - 1));
    if(i > 1 && lst > 0)
        ret = min(ret, f(i, lst - 1) + dis(L[i - 1] - 1, L[i] - lst));
    return -1 + (dp[i][lst] = ret + 1);
}


ll min_total_length(vi r, vi b) {
    for(int i = 0;i < N;i++) dp[i].clear();
    ll S_r = 0, S_b = 0;
	for(int x : r) v.PB({x, 1});
	for(int x : b) v.PB({x, 0});
	sort(v.begin(), v.end());
	int l = 0, ll = 0, gr = 0;
	for(int i = 0;i < v.size();i++){
        prf[i] = (long long)(v[i].X) + (i ? prf[i - 1] : 0);
        if(v[i].Y != l && i != 0){
            if(gr)
                rv[gr] = G[gr - 1] + rv[gr - 1];
            G[gr] = i - ll;
            L[gr] = ll;
            R[gr++] = i - 1;
           // printf("grupa %d : %d %d S %d\n", gr - 1, L[gr - 1], R[gr - 1], G[gr - 1]);
            ll = i;
        }
        l = v[i].Y;
	}
	rv[gr] = G[gr - 1] + rv[gr - 1];
	G[gr] = v.size() - ll; L[gr] = ll; R[gr] = v.size() - 1;
	n = ++gr; L[n] = v.size();
	//printf("grupa %d : %d %d S %d\n", gr - 1, L[gr - 1], R[gr - 1], G[gr - 1]);
    return f(0, 0);
}

// ovo zakomentirati prilkom submita
/**

int main(){
    int n, m, xx; scanf("%d%d", &n, &m);
    vi v1, v2;
    for(;n--;) scanf("%d", &xx), v1.PB(xx);
    for(;m--;) scanf("%d", &xx), v2.PB(xx);
    printf("%lld\n", min_total_length(v1, v2));
}
**/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(vi, vi)':
wiring.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < v.size();i++){
                ~~^~~~~~~~~~
wiring.cpp:69:8: warning: unused variable 'S_r' [-Wunused-variable]
     ll S_r = 0, S_b = 0;
        ^~~
wiring.cpp:69:17: warning: unused variable 'S_b' [-Wunused-variable]
     ll S_r = 0, S_b = 0;
                 ^~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45