제출 #1330294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330294		bradley0927	Just Long Neckties 2 (JOI25_ho_t4)	C++20	컴파일 에러	0 ms	0 KiB

Main

#include <iostream>
#include <vector>
#include <map>;
using namespace std;

vector<int> v;
int n;
map<vector<int>, int> dp[21][2];//dp[idx][ignore(t/f)][state]

int dfs(vector<int> &state, int idx, int prev) {//prev = 0 => false, prev = 1 => true (previous skipped)
    if (dp[idx][prev].find(state) != dp[idx][prev].end()) return dp[idx][prev][state];
    //ignore previous, state stored in decreasing order
    if (idx == n) return state.size();
    int cnt = INT_MAX;

    // case 1. ignore current idx
    if (prev == 0) cnt = min(cnt, dfs(state, idx + 1, 1));

    // case 2. add current
    // find largest tie smaller than current
    auto it = lower_bound(state.begin(), state.end(), v[idx], greater<int>());
    // finds first element <= x
    if (it == state.end()) {
        state.push_back(v[idx]);//cant find any tie => add to end (smallest)
        cnt = min(cnt, dfs(state, idx+1, 0));
        state.pop_back();
    } else {
        int old = *it;
        *it = v[idx];
        cnt = min(cnt, dfs(state, idx+1, 0));
        *it = old;
    }
    return dp[idx][prev][state] = cnt;
}

int main() {
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<int> state;
    cout << dfs(state, 0, 0) << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:3:15: warning: extra tokens at end of #include directive
    3 | #include <map>;
      |               ^
Main.cpp: In function 'int dfs(std::vector<int>&, int, int)':
Main.cpp:14:15: error: 'INT_MAX' was not declared in this scope
   14 |     int cnt = INT_MAX;
      |               ^~~~~~~
Main.cpp:4:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    3 | #include <map>;
  +++ |+#include <climits>
    4 | using namespace std;
Main.cpp:21:26: error: no matching function for call to 'lower_bound(std::vector<int>::iterator, std::vector<int>::iterator, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, std::greater<int>)'
   21 |     auto it = lower_bound(state.begin(), state.end(), v[idx], greater<int>());
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/string:51,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from Main.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note: candidate: 'template<class _ForwardIterator, class _Tp> constexpr _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1498 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note:   template argument deduction/substitution failed:
Main.cpp:21:26: note:   candidate expects 3 arguments, 4 provided
   21 |     auto it = lower_bound(state.begin(), state.end(), v[idx], greater<int>());
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~