제출 #1107067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1107067		Requiem	전선 연결 (IOI17_wiring)	C++17	0 / 100	11 ms	63824 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "wiring"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;

/**
Ta cần phải:
- Ghép nối các thằng đó sao cho mỗi thằng đỏ luôn được nối với 1 thằng xanh và chi phí nối là nhỏ nhất.
- Chi phí ghép nối giữa thằng i và j là abs(p[i] - p[j]).


subtask 1: n <= 200, m <= 200

dp_i_j_k: xét đến vị trí i, còn j thằng đỏ chưa đc ghép cặp, còn k thằng xanh chưa đc ghép cặp.
dp_i_j_k --> dp_(i + 1)_(j - 1)_k (nếu j > 0 va thang i + 1 la xanh)
         --> dp_(i + 1)_j_(k - 1) (neu k > 0 va thang i + 1 la đỏ)
         --> dp_(i + 1)_(j + 1)_k
         --> dp_(i + 1)_j_(k + 1)
         --> dp_(i + 1)_0_k nếu ko còn thằng đối màu để ghép
**/

namespace subtask1{
    bool check(vector<int> r, vector<int> b){
        return r.size() <= 200 and b.size() <= 200;
    }
    int n,m ;

    ll dp[201][201][201], lastRed = 0, lastBlue = 0;

    struct point{
        ll x;
        ll color;
        point(ll _x = 0, ll _color = 0): x(_x), color(_color) {}

        bool operator < (const point &other) const {
            return x < other.x;
        }
    };
    vector<point> p;
    ll solve(vector<int> r, vector<int> b){
        n = r.size();
        m = b.size();
        FOR(i, 0, n - 1){
            p.pb(point(r[i], 0));
        }
        FOR(i, 0, m - 1){
            p.pb(point(b[i], 1));
        }
        sort(p.begin(), p.end());

        memset(dp, 0x3f, sizeof(dp));
        dp[0][0][0] = 0;

        lastRed = -1, lastBlue = -1;

        FOR(i, 0, (int) p.size() - 1){
//            cout << p[i].x << ' ' << p[i].color << endl;
            FOR(remainingRed, 0, n){
                FOR(remainingBlue, 0, m){
                    if (dp[i][remainingRed][remainingBlue] < inf){
                        if (p[i].color == 0) {  //bi do
                            if (remainingBlue > 0) minimize(dp[i + 1][remainingRed][remainingBlue - 1],
                                                            dp[i][remainingRed][remainingBlue] + p[i].x);  //dong 1 bi do

                            if (remainingBlue == 0 and lastBlue != -1) minimize(dp[i + 1][remainingRed][remainingBlue],
                                                                                dp[i][remainingRed][remainingBlue] + p[i].x - lastBlue); //ghep voi 1 thang da dc ghep

                            minimize(dp[i + 1][remainingRed + 1][remainingBlue], dp[i][remainingRed][remainingBlue] - p[i].x);  //mo 1 thang bi do
                        }

                        else{
                            if (remainingRed > 0) minimize(dp[i + 1][remainingRed - 1][remainingBlue],
                                                            dp[i][remainingRed][remainingBlue] + p[i].x);  //dong 1 bi do

                            if (remainingBlue == 0 and lastRed != -1) minimize(dp[i + 1][remainingRed][remainingBlue],
                                                                                dp[i][remainingRed][remainingBlue] + p[i].x - lastRed); //ghep voi 1 thang da dc ghep

                            minimize(dp[i + 1][remainingRed][remainingBlue + 1], dp[i][remainingRed][remainingBlue] - p[i].x);  //mo 1 thang bi do
                        }

                    }
                }
            }
            if (p[i].color == 0) lastRed = p[i].x;
            else lastBlue = p[i].x;
        }
        return dp[(int)p.size()][0][0];
    }
}
ll min_total_length(vector<int> r, vector<int> b){

    if (subtask1::check(r, b)) return subtask1::solve(r, b);
  return 0;
}

/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

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