Submission #504174

# Submission time Handle Problem Language Result Execution time Memory
504174 2022-01-10T01:10:08 Z maximumSHOT Aliens (IOI16_aliens) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int inf = 1e9;
const ll inf64 = 1e18;

struct output {
    ll res;

    void print() {
        cout << res << "\n";
    }

    bool operator == (const output& o) const {
        return res == o.res;
    }
};

struct input {
    int n, m, k;
    vector<pii> a;

    input() = default;

    void read() {
        cin >> n >> m >> k;
        a.resize(n);
        for (auto& [x, y] : a)
            cin >> x >> y;
    }

    void print() {
        cout << n << " " << m << " " << k << "\n";
        for (auto [x, y] : a)
            cout << x << " " << y << "\n";
    }

    void gen() {
        static mt19937 rnd(42);
        const int MAXN = 5;
        n = rnd() % MAXN + 1;
        m = rnd() % MAXN + 1;
        k = rnd() % n + 1;
        a.resize(n);
        for (auto& [x, y] : a) {
            x = rnd() % m;
            y = rnd() % m;
        }
    }

    void gen_max_test() {

    }

    void prepare() {
        for (auto& [x, y] : a) {
            if (y > x)
                swap(x, y);
        }
        vector<pii> st;
        for (int i = 0; i < n; i++) {
            if (i > 0 && a[i].first == a[i - 1].first)
                continue;
            while (!st.empty() && st.back().second >= a[i].second)
                st.pop_back();
            st.push_back(a[i]);
        }
        a = st;
        n = (int) a.size();
    }

    ll f(int len) {
        return 1ll * len * len;
    }

    output fast() {
        prepare();
        vector<ll> rem(n);
        for (int j = 0; j < n; j++)
            rem[j] = f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
        vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                ll cost = f(a[i].first - a[j].second + 1) - rem[j];
                for (int c = 1; c <= k; c++)
                    dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
            }
        }
        ll res = inf64;
        for (int c = 1; c <= k; c++)
            res = min(res, dp[n - 1][c]);
        return output{res};
    }

    output slow() {
#ifndef DEBUG
        throw;
#endif
        prepare();
        vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                ll cost =
                        f(a[i].first - a[j].second + 1) -
                        f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
                for (int c = 1; c <= k; c++)
                    dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
            }
        }
        ll res = inf64;
        for (int c = 1; c <= k; c++)
            res = min(res, dp[n - 1][c]);
        return output{res};
    }
};

void test_case() {
    input in;
    in.read();
    output res = in.fast();
    res.print();
}

void work() {
    int t = 1;
    while (t--)
        test_case();
}

void test() {
    for (int t = 1;;t++) {
        input in;
        in.gen();
        input in_fs = in;
        input in_sl = in;
        output fs = in_fs.fast();
        output sl = in_sl.slow();
        if (fs == sl) {
            cout << "OK" << endl;
            fs.print();
            cout << "\n=========" << endl;
        } else {
            cout << "WA " << t << "\n";
            cout << "exp\n";
            sl.print();
            cout << "\n=========\n";
            cout << "fnd\n";
            fs.print();
            cout << "\n=========\n";
            in.print();
            break;
        }
    }
}

void max_test() {
    input in;
    in.gen_max_test();
    input in_fs = in;
    output fs = in_fs.fast();
    fs.print();
}

#ifdef DEBUG

int main() {

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    work();
//    test();
//    max_test();

    return 0;
}
#else

ll take_photos(int n, int m, int k, int[] r, int[] c) {
    input in;
    in.n = n;
    in.m = m;
    in.k = k;
    in.a.resize(n);
    for (int i = 0; i < n; i++)
        in.a[i] = {r[i], c[i]};
    output fs = in.fast();
    return fs.res;
}

#endif

Compilation message

aliens.cpp:191:43: error: expected ',' or '...' before 'r'
  191 | ll take_photos(int n, int m, int k, int[] r, int[] c) {
      |                                           ^
aliens.cpp: In function 'll take_photos(int, int, int, int*)':
aliens.cpp:198:20: error: 'r' was not declared in this scope
  198 |         in.a[i] = {r[i], c[i]};
      |                    ^
aliens.cpp:198:26: error: 'c' was not declared in this scope
  198 |         in.a[i] = {r[i], c[i]};
      |                          ^
aliens.cpp:198:30: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} and '<brace-enclosed initializer list>')
  198 |         in.a[i] = {r[i], c[i]};
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<int, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<int, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<int, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<int, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
aliens.cpp:198:30: note:   couldn't deduce template parameter '_U1'
  198 |         in.a[i] = {r[i], c[i]};
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
aliens.cpp:198:30: note:   couldn't deduce template parameter '_U1'
  198 |         in.a[i] = {r[i], c[i]};
      |                              ^