제출 #989472

#제출 시각아이디문제언어결과실행 시간메모리
989472khanhtb수열 (APIO14_sequence)C++14
0 / 100
49 ms131072 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld double #define pb push_back #define pf push_front #define vi vector<ll> #define vii vector<vi> #define pll pair<ll,ll> #define vpll vector<pll> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const ll mod = 1e9+7; const ll inf = 1e18; const ll base = 31; const ll blocksz = 320; const ll N = 1e5+8; ll pre[N],pre2[N],n,a[N],dp[N][201],k,trace[N][201]; ll cost(ll l, ll r){ return ((pre[r]-pre[l-1])*(pre[r]-pre[l-1])-(pre2[r]-pre2[l-1]))/2; } void dnc(ll l, ll r, ll optl, ll optr, ll j){ if(l > r) return; ll m = l+r>>1; pll best = {inf,-1}; for(ll i = optl; i < min(m,optr); i++){ best = min(best,{dp[i][j-1]+cost(i+1,m),i}); } dp[m][j] = best.fi; ll opt = best.se; trace[m][j] = opt; dnc(l,m-1,optl,opt,j); dnc(m+1,r,opt,optr,j); } void solve(){ cin >> n >> k; k++; for(ll i = 1; i <= n; i++){ cin >> a[i]; pre[i] = pre[i-1]+a[i]; pre2[i] = pre2[i-1]+a[i]*a[i]; } for(ll i = 1; i <= n; i++) dp[i][1] = cost(1,i),trace[i][1] = i; for(ll j = 2; j <= k; j++) dnc(1,n,1,n,j); cout << cost(1,n)-dp[n][k] << '\n'; vi ans; for(ll i = n; k && i != -1; i = trace[i][k],k--) ans.pb(i); reverse(all(ans)); ans.pop_back(); for(ll i:ans) cout << i << " "; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if(fopen("test.inp","r")){ freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } // freopen("SSEQ.inp","r",stdin); // freopen("SSEQ.out","w",stdout); ll T = 1; // cin >> T; while(T--){ solve(); cout << '\n'; } }

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

sequence.cpp: In function 'void dnc(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     ll m = l+r>>1;
      |            ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("test.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...