제출 #42876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42876		MatheusLealV	전선 연결 (IOI17_wiring)	C++14	30 / 100	292 ms	79636 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef long long ll;

ll n, m, r[N], b[N], dp[500][500];

ll solve(int i, int j)
{
    if(!i && !j) return 0LL;

    if(!i || !j) return inf;

    if(dp[i][j] != -1) return dp[i][j];

    return dp[i][j] = min(solve(i - 1, j), min(solve(i, j - 1), solve(i - 1, j - 1))) + abs(r[i] - b[j]);
}

ll dp2[N][70], cnt;

map<int, int> mapa;

int pos[N][2];

ll solve2(int i, int j)
{
    if(!i && !j) return 0LL;

    if(!i || !j || (abs(pos[i][0] - pos[j][1]) > 20)) return inf;

    int dj = 21 + pos[i][0] - pos[j][1];

    if(dp2[i][dj] != -1) return dp2[i][dj];

    return dp2[i][dj] = min(solve2(i - 1, j), min(solve2(i, j - 1), solve2(i - 1, j - 1))) + abs(r[i] - b[j]);
}

ll custo(vector<int> esq, vector<int> dir)
{
    if(esq.empty() || dir.empty()) return inf;

    if(dir.back() < esq.front()) swap(esq, dir);

    if(esq.back() > dir.front()) return inf;

    ll sum_red = 0, sum_blue = 0;

    for(auto x: esq) sum_red -= x;

    for(auto x: dir) sum_blue += x;

    sum_red += esq.size()*((ll)esq.back()), sum_blue -= dir.size()*((ll)dir.front());

    return max(esq.size(), dir.size())*(dir.front() - esq.back()) + sum_blue + sum_red;
}

ll min_total_length(vector<int> esq, vector<int> dir)
{
    n = esq.size(), m = dir.size();

    vector<int> all;

    for(int i = 1; i <= n; i++) r[i] = esq[i - 1], all.push_back(esq[i - 1]);

    for(int i = 1; i <= m; i++) b[i] = dir[i - 1], all.push_back(dir[i - 1]);

    sort(all.begin(), all.end());

    for(int i = 0; i < all.size(); i++)
    {
        if(!mapa[all[i]]) mapa[all[i]] = ++cnt;
    }

    for(int i = 1; i <= n; i++) pos[i][0]= mapa[r[i]];

    for(int j = 1; j <= m; j++) pos[j][1] = mapa[b[j]];

    memset(dp, -1, sizeof dp);

    memset(dp2, -1, sizeof dp2);

    if(esq.back() < dir.front()) return custo(esq, dir);

    if(n <= 1000) return solve(n, m);

    return solve2(n, m);
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < all.size(); i++)
                      ^

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