제출 #989639

#제출 시각아이디문제언어결과실행 시간메모리
989639khanhtb수열 (APIO14_sequence)C++14
71 / 100
59 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][2],k,trace[N][201]; ll cost(ll l, ll r){ return (pre[r]-pre[l-1])*pre[l-1]; } 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 = max(best,{dp[i-1][(j&1)^1]+cost(i,m),i}); } dp[m][j&1] = best.fi; ll opt = best.se; trace[m][j] = opt-1; dnc(l,m-1,optl,opt,j); dnc(m+1,r,opt,optr,j); } void solve(){ cin >> n >> k; for(ll i = 1; i <= n; i++){ cin >> a[i]; pre[i] = pre[i-1]+a[i]; } for(ll j = 1; j <= k; j++) dnc(1,n,1,n,j); cout << dp[n][k&1] << '\n'; vi ans; for(ll i = k; i; i--){ n = trace[n][i]; ans.pb(n); } reverse(all(ans)); 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:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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.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...