Submission #584031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584031	2022-06-26T16:57:49 Z	yanndev	Toy Train (IOI17_train)	C++17	Compilation error	0 ms	0 KB

train

#include <bits/stdc++.h>
#define int long long
using namespace std;

// 13pts at 47mn
const int OO = 1e16;

int n, m;
int dp[201][201];
vector<int> R {};
vector<int> B {};

int solve(int rPos, int bPos) {
    if (rPos == n && bPos == m)
        return 0;
    if (rPos == n || bPos == m)
        return OO;
    if (dp[rPos][bPos] != -1)
        return dp[rPos][bPos];
    
    // link rPos and bPos and then extend to one of them
    int dif = abs(R[rPos] - B[bPos]);
    return dp[rPos][bPos] = dif + min({solve(rPos + 1, bPos), solve(rPos, bPos + 1), solve(rPos + 1, bPos + 1)});
}

int min_total_length(vector<int> r, vector<int> b) {
    R = r;
    B = b;
    n = (int)r.size();
    m = (int)b.size();
    
    if (n <= 200 && m <= 200) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                dp[i][j] = -1;
        return solve(0, 0);
    }

    int ans = 0;

    if ((int)r.size() > (int)b.size()) {
        for (int i = 0; i < (int)b.size(); i++) {
            //cout << "blue " << i << " red " << (int)r.size() - i - 1 << '\n';
            ans += b[i] - r[(int)r.size() - i - 1];
        }
        for (int j = (int)r.size() - (int)b.size() - 1; j >= 0; j--) {
            //cout << "blue " << 0 << " red " << j << '\n';
            ans += b[0] - r[j];
        }
    } else {
        for (int i = 0; i < (int)r.size(); i++)
            ans += b[(int)r.size() - i - 1] - r[i];
        for (int j = (int)r.size(); j < (int)b.size(); j++)
            ans += b[j] - r.back();
    }

    return ans;
}

signed main() {
    vector<int> r {1, 2};
    vector<int> b {3, 4, 5};
    cout << min_total_length(r, b) << '\n';
    return 0;
}

Compilation message

/usr/bin/ld: /tmp/ccFlkAAx.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccT0m9ht.o:train.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccFlkAAx.o: in function `main':
grader.cpp:(.text.startup+0x29f): undefined reference to `who_wins(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status