제출 #851403

#제출 시각아이디문제언어결과실행 시간메모리
851403treap_enjoyer수열 (APIO14_sequence)C++14
0 / 100
70 ms131072 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("Ofast,unroll-loops") #define ll long long #define all(x) x.begin(), x.end() using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll INF = 1e18; const int MAXN = 1e5 + 5; struct line{ ll k; ll c; ll num; ll calc(ll x){ return k * x + c; } ll intersec(line b){ if(k == b.k){ if(c == b.c) return INF; else return -INF; } else return (c - b.c) / (b.k - k); } }; vector<pair<line, ll> > st; vector<ll> seg; vector<line> seglines; int cur; int pos; void add(line a){ if(st.size() == 0){ st.push_back({a, INF}); //cout << st[st.size() - 1].first.c << " " << st[st.size() - 1].first.k << endl; seg[st.size()] = INF; seglines[st.size()] = a; pos = 1; return; } if(st.size() == 1){ if(a.k == st.back().first.k){ if(a.c > st.back().first.c){ seglines[1] = a; st.back().first = a; //cout << st.back().first.k << " " << st.back().first.c << endl; return; } } else{ int pos = a.intersec(st.back().first); st[st.size() - 1].second = pos; seg[st.size()] = pos; st.push_back({a, INF}); seg[st.size()] = INF; seglines[st.size()] = a; //cout << st[st.size() - 1].first.k << " " << st[st.size() - 1].first.c << endl; return; } } line b = st[st.size() - 1].first; if(a.k == b.k){ if(a.c <= b.c) return; else{ if(pos == st.size()){ pos--; } st.pop_back(); st.back().second = INF; seg[st.size()] = INF; add(a); return; } } else{ st.pop_back(); line c = st.back().first; if(a.intersec(c) <= st.back().second){ //cout << a.k << " " << a.c << " -- " << b.k << " " << b.c << " --- " << c.k << " " << c.c << " " << a.intersec(c) << " " << st.back().second << endl; if(pos == st.size() + 1){ pos--; } seg[st.size()] = INF; st.back().second = INF; add(a); return; } else{ int x = a.intersec(b); if(pos == st.size() && x < cur){ pos++; } st.push_back({b, x}); seg[st.size()] = x; st.push_back({a, INF}); seg[st.size()] = INF; seglines[st.size()] = a; return; } } } void upd(int x){ while(seg[pos] <= x){ pos++; } cur = x; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //ifstream cin("input.txt"); //ofstream cout("output.txt"); int n, k; cin >> n >> k; vector<ll> a(n + 1); for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<vector<ll> > dp(k + 2, vector<ll>(n + 2, -INF)); vector<vector<int> > p(k + 2, vector<int>(n + 2, 0)); dp[0][0] = 0; vector<ll> pref(n + 2, 0); for(int i = 1; i <= n; i++){ pref[i] += pref[i - 1]; pref[i] += a[i]; } for(int i = 1; i <= k + 1; i++){ st.clear(); seg.clear(); seglines.clear(); seg.resize(n + 1, -INF); seglines.resize(n + 1); cur = pref[1]; pos = 1; // cout << i << ": " << endl; for(int j = 1; j <= n; j++){ // cout << pref[j - 1] << " <> " << dp[i - 1][j - 1] - pref[j - 1] * pref[j - 1] << endl; if(dp[i - 1][j - 1] != -INF){ add({pref[j - 1], dp[i - 1][j - 1] - pref[j - 1] * pref[j - 1], j - 1}); upd(pref[j]); } if(st.size() && seglines[pos].calc(pref[j]) > dp[i][j]){ dp[i][j] = seglines[pos].calc(pref[j]); p[i][j] = seglines[pos].num; } /*for(int k = 0; k < st.size(); k++){ cout << "(" << st[k].first.k << " + " << st[k].first.c << ")" << endl; } cout << "---------" << endl;*/ } } vector<int> ans; /*for(int i = 0; i <= k + 1; i++){ for(int j = 0; j <= n; j++){ cout << dp[i][j] << " "; } cout << endl; }*/ int cur = n; for(int i = k; i > 0; i--){ ans.push_back(p[i + 1][cur]); cur = p[i + 1][cur]; } cout << dp[k + 1][n] << endl; reverse(all(ans)); for(auto i: ans){ cout << i << " "; } }

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

sequence.cpp: In function 'void add(line)':
sequence.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if(pos == st.size()){
      |                ~~~~^~~~~~~~~~~~
sequence.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             if(pos == st.size() + 1){
      |                ~~~~^~~~~~~~~~~~~~~~
sequence.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             if(pos == st.size() && x < cur){
      |                ~~~~^~~~~~~~~~~~
#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...