| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1131018 | dibamboo | Feast (NOI19_feast) | C++20 | Compilation error | 0 ms | 0 KiB |
/* author : Dinmukhammed ^_^ */
#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#include <complex>
using namespace std;
#define F first
#define S second
#define sz size()
#define ll long long
#define ld long double
#define int ll
const int N = 4e5+3;
const ll inf = 1e18;
ll a[N] , p[N];
pair <ll , int> dp[N];
int n;
pair <ll , int> get(ll lam){
dp[0] = {0ll , (int)0};
set <pair <ll , int>> st;
pair <ll , int> mx = dp[0];
for(int i = 1; i <= n; i++){
mx = max({dp[i - 1].F - p[i] , dp[i - 1].S} , mx);
dp[i] = mx;
dp[i].F += lam + p[i];
dp[i].S--;
dp[i] = max(dp[i - 1] , dp[i]);
mx = max({dp[i].F - p[i] , dp[i].S} , mx);
}
dp[n].S = -dp[n].S;
return dp[n];
}
void Main(){
ll k; cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
ll l = -(ll)1e18 , r = (ll)1e18 , res = -(ll)1e18;
while(r >= l){
ll md = (r + l) / 2;
if(get(md).S <= k){
res = md;
l = md + 1;
}
else r = md - 1;
}
cout << get(res).F - res * k;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--) Main();
}Compilation message (stderr)
feast.cpp: In function 'std::pair<long long int, long long int> get(long long int)':
feast.cpp:54:65: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and 'long long int')
54 | mx = max({dp[i - 1].F - p[i] , dp[i - 1].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:418:9: note: candidate: 'template<class _U1, class _U2> constexpr 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 = long long int; _T2 = long long int]'
418 | operator=(const pair<_U1, _U2>& __p)
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:418:9: note: template argument deduction/substitution failed:
feast.cpp:54:65: note: mismatched types 'const std::pair<_T1, _T2>' and 'long long int'
54 | mx = max({dp[i - 1].F - p[i] , dp[i - 1].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:430:9: note: candidate: 'template<class _U1, class _U2> constexpr 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 = long long int; _T2 = long long int]'
430 | operator=(pair<_U1, _U2>&& __p)
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:430:9: note: template argument deduction/substitution failed:
feast.cpp:54:65: note: mismatched types 'std::pair<_T1, _T2>' and 'long long int'
54 | mx = max({dp[i - 1].F - p[i] , dp[i - 1].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:390:7: note: candidate: 'constexpr 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 = long long int; _T2 = long long 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<long long int, long long int>&]'
390 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:393:55: note: no known conversion for argument 1 from 'long long int' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long 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++/11/bits/stl_pair.h:401:7: note: candidate: 'constexpr 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 = long long int; _T2 = long long 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<long long int, long long int>&&]'
401 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:404:45: note: no known conversion for argument 1 from 'long long int' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
401 | operator=(typename conditional<
| ~~~~~~~~~~~~~~~~~~~~~
402 | __and_<is_move_assignable<_T1>,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
403 | is_move_assignable<_T2>>::value,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
404 | pair&&, __nonesuch&&>::type __p)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
feast.cpp:59:57: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and 'long long int')
59 | mx = max({dp[i].F - p[i] , dp[i].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:418:9: note: candidate: 'template<class _U1, class _U2> constexpr 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 = long long int; _T2 = long long int]'
418 | operator=(const pair<_U1, _U2>& __p)
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:418:9: note: template argument deduction/substitution failed:
feast.cpp:59:57: note: mismatched types 'const std::pair<_T1, _T2>' and 'long long int'
59 | mx = max({dp[i].F - p[i] , dp[i].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:430:9: note: candidate: 'template<class _U1, class _U2> constexpr 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 = long long int; _T2 = long long int]'
430 | operator=(pair<_U1, _U2>&& __p)
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:430:9: note: template argument deduction/substitution failed:
feast.cpp:59:57: note: mismatched types 'std::pair<_T1, _T2>' and 'long long int'
59 | mx = max({dp[i].F - p[i] , dp[i].S} , mx);
| ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/stl_pair.h:390:7: note: candidate: 'constexpr 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 = long long int; _T2 = long long 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<long long int, long long int>&]'
390 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:393:55: note: no known conversion for argument 1 from 'long long int' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long 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++/11/bits/stl_pair.h:401:7: note: candidate: 'constexpr 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 = long long int; _T2 = long long 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<long long int, long long int>&&]'
401 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/11/bits/stl_pair.h:404:45: note: no known conversion for argument 1 from 'long long int' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
401 | operator=(typename conditional<
| ~~~~~~~~~~~~~~~~~~~~~
402 | __and_<is_move_assignable<_T1>,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
403 | is_move_assignable<_T2>>::value,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
404 | pair&&, __nonesuch&&>::type __p)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
from /usr/include/c++/11/bits/stl_tree.h:63,
from /usr/include/c++/11/map:60,
from feast.cpp:3:
/usr/include/c++/11/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = const long long int*; _Iterator2 = const long long int*; _Compare = std::pair<long long int, long long int>]':
/usr/include/c++/11/bits/stl_algo.h:5688:12: required from 'constexpr _ForwardIterator std::__max_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = const long long int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<std::pair<long long int, long long int> >]'
/usr/include/c++/11/bits/stl_algo.h:5739:43: required from 'constexpr _FIter std::max_element(_FIter, _FIter, _Compare) [with _FIter = const long long int*; _Compare = std::pair<long long int, long long int>]'
/usr/include/c++/11/bits/stl_algo.h:3468:31: required from 'constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare) [with _Tp = long long int; _Compare = std::pair<long long int, long long int>]'
feast.cpp:54:11: required from here
/usr/include/c++/11/bits/predefined_ops.h:158:30: error: no match for call to '(std::pair<long long int, long long int>) (const long long int&, const long long int&)'
158 | { return bool(_M_comp(*__it1, *__it2)); }
| ~~~~~~~^~~~~~~~~~~~~~~~