답안 #626283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626283	2022-08-11T10:53:46 Z	jeroenodb	메기 농장 (IOI22_fish)	C++17	컴파일 오류	0 ms	0 KB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const ll oo = 1e18;
void cmax(ll& a, ll b) {a=max(a,b);}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vvi ys(N+1);
    bool allEven=1;
    ll total=0;
    for(int i=0;i<M;++i) {
        if(X[i]%2!=0) allEven=0;
        Y[i]++,X[i]++;
        total+=W[i];
        ys[X[i]].push_back(i);
    }

    vector<vector<ll>> pref(N+1,{0});
    {
    int x=0;
    for(auto& v : ys) {
        sort(all(v),[&](int i, int j) {return Y[i]<Y[j];});
        for(auto& id : v) {
            pref[x].push_back(W[id]);
            id = Y[id];
        }
        v.insert(v.begin(),0);
        partial_sum(all(pref[x]),pref[x].begin());
        x++;
    }
    }
    // dynamic programming
    // DP[column][y-pos][state] 
    // state {0: rising, 1: falling}
    // transition going up: 
    array<vector<ll>,2> dp = {vector<ll>{0LL},{-oo}};
    ll top = -oo;
    auto getS = [&](int x, int y) {
        auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
        return pref[x][i];
    };
    for(int x=1;x<=N;++x) {
        int k = ys[x].size();
        array<vector<ll>,2> ndp = {vector<ll>(k,-oo),vector<ll>(k,-oo)};
        // falling to falling
        {
        int j = ys[x-1].size()-1;
        ll best = -oo;
        for(int i=k-1;i>=0;--i) {
            while(j>=0 and ys[x-1][j]>=ys[x][i]) {
                cmax(best,dp[1][j]);
                --j;
            }
            cmax(ndp[1][i], best-getS(x-1,ys[x][i]) + pref[x][i]);
        }
        }
        // rising to rising
        {
        int j = 0;
        ll best = -oo;
        for(int i=0;i<k;++i) {
            while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
                cmax(best,dp[0][j]-getS(x,ys[x-1][j]));
                --j;
            }
            cmax(ndp[0][i], best + pref[x][i]);
        }
        }
        // falling to rising, case 1
        {
        ll best = *max_element(all(dp[1]));
        for(int i=0;i<k;++i) 
            cmax(ndp[0][i],best+pref[x][i]);
        }
        // falling to rising, spaced one apart. 
        {
        int j = 0;
        ll best = -oo;
        for(int i=0;i<k;++i) {
            while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
                cmax(best,dp[1][j]-pref[x][i]-pref[x-1][j]);
                --j;
            }
            cmax(ndp[0][i], best + pref[x][i] + getS(x-1, ys[x][i]));
        }

        }
        // top to falling
        for(int i=0;i<k;++i) {
            cmax(ndp[1][i],pref[x][i]+top);
        }
        // rising to top
        cmax(top,*max_element(all(dp[0])));

        swap(dp,ndp);
    }
    // falling or top
    
    return max(top,*max_element(all(dp[1])));
    
}

Compilation message

fish.cpp: In lambda function:
fish.cpp:47:67: error: no matching function for call to 'max(long long int, __gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type)'
   47 |         auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
      |                                                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
fish.cpp:47:67: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
   47 |         auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
      |                                                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
fish.cpp:47:67: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
   47 |         auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
      |                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from fish.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
fish.cpp:47:67: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   47 |         auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
      |                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from fish.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
fish.cpp:47:67: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   47 |         auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1);
      |                                                                   ^