제출 #745006

#제출 시각아이디문제언어결과실행 시간메모리
745006sudheerays123수열 (APIO14_sequence)C++17
50 / 100
690 ms16772 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int const ll N = 1000+5 , K = 200+5 , INF = 1e18 , MOD = 1e9+7; ll n,k; ll dp[N][N],opt[N][N]; vector<ll> presum(N); ll go(ll i , ll j){ if(j < 0) return -INF; if(i == 0){ if(j > 0) return -INF; return 0; } if(dp[i][j] != -1) return dp[i][j]; ll ans = -INF,ind; for(ll k = 1; k <= i; k++){ ll cur = go(k-1,j-1)+ presum[k-1]*(presum[i]-presum[k-1]); if(cur > ans){ ans = cur; ind = k-1; } } opt[i][j] = ind; return dp[i][j] = ans; } void solve(){ cin >> n >> k; vector<ll> a(n+5); for(ll i = 1; i <= n; i++) cin >> a[i]; for(ll i = 1; i <= n; i++) presum[i] = presum[i-1]+a[i]; memset(dp,-1,sizeof dp); cout << go(n,k+1) << "\n"; ll curi = n , curj = k+1; vector<ll> path; while(true){ curi = opt[curi][curj]; curj--; if(curi == 0) break; path.push_back(curi); } reverse(path.begin(),path.end()); for(auto u : path) cout << u << " "; } int main(){ fast; ll tc = 1; // cin >> tc; while(tc--) solve(); return 0; }

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

sequence.cpp: In function 'long long int go(long long int, long long int)':
sequence.cpp:31:12: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  opt[i][j] = ind;
      |  ~~~~~~~~~~^~~~~
#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...