Submission #173927

#	Time	Username	Problem	Language	Result	Execution time	Memory
173927		gs18103	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

vector <pll> line;
double cross(pll a, pll b) {return (double)(b.se - a.se) / (a.fi - b.fi);}

void add_line(pll l) {
    while(line.size() >= 2) {
        pll l1 = line[line.size()-2], l2 = line[line.size()-1];
        if(cross(l1, l2) < cross(l2, l)) break;
        line.pop_back();
    }
    line.eb(l);
}

//solution for nk log n
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pll> tarr, arr;
    vector < vector <ll> > dp;
    dp.resize(k+3);
    for(int i = 0; i < n; i++) {
        if(r[i] < c[i]) swap(r[i], c[i]);
        r[i]++;
        tarr.eb(r[i], c[i]);
    }
    sort(all(tarr));
    arr.eb(0, -1);
    for(int i = 0; i < n; i++) {
        while(!arr.empty() && arr.back().se >= tarr[i].se) arr.pop_back();
        arr.eb(tarr[i]);
    }
    n = arr.size() - 1;
    k = min(n, k);
    dp[1].resize(n+1);
    for(int i = 1; i <= n; i++) dp[1][i] = (arr[i].fi - arr[1].se) * (arr[i].fi - arr[1].se);
    for(int i = 2; i <= k; i++) {
        dp[i].resize(n+1);
        int idx = 0;
        while(!line.empty()) line.pop_back();
        add_line(make_pair(-2*arr[1].se, arr[1].se * arr[1].se));
        for(int j = 1; j <= n; j++) {
            while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
            dp[i][j] = arr[j].fi * arr[j].fi + line[idx].fi * arr[j].fi + line[idx].se;
            if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
        }
    }
    return dp[k][n];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
                   ~~~~~~~~^~~~~~~~~~~~~
aliens.cpp:59:127: error: no matching function for call to 'max(int, long long int)'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                               ^
In file included from /usr/include/c++/7/vector:60:0,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:127: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                               ^
In file included from /usr/include/c++/7/vector:60:0,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:127: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:127: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:127: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                               ^
aliens.cpp:59:161: error: no matching function for call to 'max(int, long long int)'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                                                                 ^
In file included from /usr/include/c++/7/vector:60:0,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:161: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                                                                 ^
In file included from /usr/include/c++/7/vector:60:0,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:161: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                                                                 ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:161: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                                                                 ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
aliens.cpp:59:161: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
                                                                                                                                                                 ^