Submission #574515

#	Time	Username	Problem	Language	Result	Execution time	Memory
574515		2fat2code	Wiring (IOI17_wiring)	C++17	100 / 100	58 ms	12508 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 200005;

long long n, m, sum;
long long dp[nmax], calc[nmax];
vector<pair<long long, long long>>Q, vecc;
vector<long long>last, now;

void check(int urmator){
    Q.clear();
    for(int i=0;i<last.size();i++){
        calc[i+1] = calc[i] + vecc[last[i]].fr;
    }
    for(int i=0;i<last.size();i++){
        long long heh = dp[last[i]] - (calc[last.size()] - calc[i]) + (last.size() - i) * urmator;
        if(Q.size()){
            auto it = Q.back().fr;
            if(it > heh) Q.push_back({heh, last[i]});
        }
        else{
            Q.push_back({heh, last[i]});
        }
    }
}

long long min_total_length(vector<int> r, vector<int> b) {
	n = (int)r.size();
	m = (int)b.size();
	for(auto it : r) vecc.push_back({it, 0});
	for(auto it : b) vecc.push_back({it, 1});
	sort(all(vecc));
    now.push_back(0);
	long long curr = 0;
	while(vecc[curr].sc == vecc[curr + 1].sc){
        ++curr;
        now.push_back(curr);
	}
	dp[0] = 0;
	for(int i=1;i<=now.size();i++) dp[i] = 1e16;
	long long lmao = 1e16;
	while(curr < n + m){
        ++curr;
        if(curr == n + m) break;
        else if(vecc[curr].sc != vecc[curr - 1].sc){
            sum = 0;
            dp[now[0]] = min(dp[now[0]], dp[now[0]+1]);
            last = now;
            now.clear();
            check(vecc[curr].fr);
            lmao = 1e16;
        }
        now.push_back(curr);
        sum += vecc[curr].fr;
        if(Q.size()){
            if(last.back() - Q.back().sc + 1 <= curr - now[0] + 1){
                Q.pop_back();
            }
        }
        lmao = lmao + vecc[curr].fr - vecc[last.back()].fr;
        if(last[0] <= last.back() - (curr - (last.back() + 1))){
            lmao = min(lmao, sum - calc[last.size()] + calc[last.size()-(curr-(last.back()+1))-1] + dp[last.back()-(curr-(last.back()+1))]);
        }
        dp[curr+1] = lmao;
        if(Q.size()) dp[curr+1] = min(dp[curr+1], Q.back().fr+sum-(curr-now[0]+1)*vecc[now[0]].fr);

	}
	return dp[n + m];
}

Compilation message (stderr)

wiring.cpp: In function 'void check(int)':
wiring.cpp:17:18: 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<last.size();i++){
      |                 ~^~~~~~~~~~~~
wiring.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<last.size();i++){
      |                 ~^~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=1;i<=now.size();i++) dp[i] = 1e16;
      |              ~^~~~~~~~~~~~

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