Submission #1107097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107097		khanhtai	Wiring (IOI17_wiring)	C++14	7 / 100	34 ms	7740 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
Gia su n <= m.
dp[i][j]: ta da ghep thang i o r va thang j o b;
dp[i][j]: --> dp[i + 1][j] bằng cách ghép i và j.
dp[i][j]: --> dp[i][j + 1] bằng cách bỏ qua i.

dp[n][m].
**/

int n, m;
vector<int> r, b;

namespace subtask1{
    bool check(){
        return n <= 200 and m <= 200;
    }

    ll dp[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(){
        n = r.size();
        m = b.size();

        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 1; i<= n; i++){
            for(int j = 1; j <= m; j++){
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + abs(r[i - 1] - b[j - 1]);
//                cout << i << ' ' << j << ' ' << dp[i][j] << ' '<< dp[i - 1][j] <<' '<<dp[i][j - 1] << ' ' << dp[i - 1][j - 1] <<endl;
            }
        }
        return dp[n][m];

    }
}
ll min_total_length(vector<int> r1, vector<int> b1){
    r = r1;
    b = b1;
    n = r.size();
    m = b.size();
    if (subtask1::check()) return subtask1::solve();
}

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

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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