Submission #574427

#	Time	Username	Problem	Language	Result	Execution time	Memory
574427		2fat2code	전선 연결 (IOI17_wiring)	C++17	0 / 100	1 ms	316 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++){
        int 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;
            last = now;
            now.clear();
            check(vecc[curr].fr);
            lmao = 1e16;
        }
        now.push_back(curr);
        sum += vecc[curr].fr;
        if(last.back() - Q.back().sc + 1 <= curr - (last.back() + 1) + 1){
            Q.pop_back();
        }
        lmao = min(lmao + vecc[curr].fr - vecc[last.back()].fr, sum - calc[last.size()] + calc[last.size() - (curr - (last.back() + 1) + 1)] + dp[last.back() - (curr - (last.back() + 1))]);
        dp[curr + 1] = min(lmao, Q.back().fr + sum - (curr - now[0] - 1) * now[0]);
	}
	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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45