Submission #1111681

#TimeUsernameProblemLanguageResultExecution timeMemory
1111681PhcKhnhTapCodeSplit the sequence (APIO14_sequence)C++17
11 / 100
93 ms131072 KiB
#include <bits/stdc++.h> /**------------------------------------------ ---------Author: PhcKhnhTapCode ------------- ---------From: CHV with luv ❤ -------------- ---------Training To Win Voi 25 !!! --------- --------------------------------------------- ------------------MemoryLimitExeeded<YAT>-**/ using namespace std; #ifdef phckhnh_local #include "D:\Users\AdminTCT\Desktop\CODE\debug.h" #else #define debug(...) 0 #endif #define int long long #define ll long long #define db long double #define fi first #define se second #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define vvi vector<vi> #define vvvi vector<vvi> #define pub push_back #define all(v) v.begin(),v.end() #define mid(l, r) ((l + r) >> 1LL) #define left(id) (id << 1LL) #define right(id) ((id << 1LL) | 1LL) #define Mask(i) (1LL << (i)) #define Onbit(n, i) (n | Mask(i)) #define Ofbit(n, i) (n ^ Mask(i)) #define Bit(n, i) ((n >> (i)) & 1LL) #define Log2(n) (63 - __builtin_clzll(n)) #define Cntbit(n) __builtin_popcountll(n) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FOD(i, b, a) for (int i = b; i >= a; --i) #define rep(i, n) for (int i = 0; i < n; ++i) #define repd(i, n) for (int i = n - 1; ~i;--i) #define repv(v, H) for (auto &v: H) template <class T> bool maximize(T &A, const T &B) {if(A < B) {return A = B, true;} return false;} template <class T> bool minimize(T &A, const T &B) {if(A > B) {return A = B, true;} return false;} const int dx[4] = {0, +1, 0, -1}; const int dy[4] = {+1, 0, -1, 0}; const int inf = 1e9, BLOCK = 700, MAXN = 1e5 + 10; const long long oo = 1e18, BASE = 311, MOD = 1e9 + 7; //____________________________________________________________________ int n, k; ll a[MAXN]; ll dp[MAXN][205]; struct Line{ long long a, b, id; // a.x + b long long eval(long long x){ return a * x + b; } }; struct LineContainer{ const long double zero = 1e-9; deque <Line> v; void init(){ v.clear(); } bool bad(const Line &l1, const Line &l2, const Line &l3){ long double x = (long double) (l2.b - l1.b) * (l2.a - l3.a); long double y = (long double) (l3.b - l2.b) * (l1.a - l2.a); return (x - y) > zero; } // he so goc tang -> max // he so goc giam -> min void add(const Line &a){ int s = v.size(); while(s >= 2 && bad(v[s - 2], v[s - 1], a)){ v.pop_back(); s--; } v.push_back(a); } long long get(long long x) { if(v.empty()) return 0; while(v.size() >= 2 && v[0].eval(x) <= v[1].eval(x)) v.pop_front(); return v.front().eval(x); } long long get_id() { return v.front().id; } }hull; int memo[MAXN][205]; void trace(int i, int cnt) { if(cnt == 1) return ; int j = memo[i][cnt]; trace(j, cnt - 1); cout << j << ' '; } void phckhnh() { cin >> n >> k; FOR(i, 1, n) { cin >> a[i]; a[i] += a[i - 1]; } FOR(i, 1, n) dp[i][1] = 0; FOR(cnt, 2, k + 1) { hull.init(); FOR(i, 1, cnt - 1) { ll A = a[i], B = dp[i][cnt - 1] - a[i] * a[i]; hull.add({A, B, i}); } FOR(i, cnt, n) { dp[i][cnt] = hull.get(a[i]); memo[i][cnt] = hull.get_id(); ll A = a[i], B = dp[i][cnt - 1] - a[i] * a[i]; hull.add({A, B, i}); } } ll ans = -oo; FOR(cnt, 2, k + 1) maximize(ans, dp[n][cnt]); cout << ans << '\n'; trace(n, k + 1); } //____________________________________________________________________ main(){ //____________________________________________________ ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define YAT "phckhnh" if (fopen(YAT".inp", "r")) { freopen(YAT".inp", "r", stdin); freopen(YAT".out", "w", stdout); } //____________________________________________________ int Ntest = 1; // cin >> Ntest; while(Ntest--) { phckhnh(); cout << endl; } cerr <<"\nPhcKhnh's TimeRun: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s. \n"; }

Compilation message (stderr)

sequence.cpp:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main(){
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(YAT".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(YAT".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...