제출 #869324

#제출 시각아이디문제언어결과실행 시간메모리
869324prohacker수열 (APIO14_sequence)C++14
50 / 100
104 ms7272 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long using namespace std; const int N = 1010; const int INF = INT_MAX; const int mod = 1e9+7; int n,m; ll dp[N][210],ans; int s[N],trace[N][210]; stack<int> st; int get(int l, int r) { return s[r] - s[l-1]; } signed main() { if (fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1 ; i <= n ; i++) { int x; cin >> x; s[i] = s[i-1] + x; } // s[n+1] = s[n]; for(int k = 1 ; k <= m ; k++) { for(int i = k ; i <= n ; i++) { for(int j = i-1 ; j >= 0 ; j--) { if(dp[j][k-1]+1LL*(s[i]-s[j])*(s[n]-s[i]) > dp[i][k]) { dp[i][k] = dp[j][k-1]+1LL*(s[i]-s[j])*(s[n]-s[i]); trace[i][k] = j; } } } } int id; ans = -1; for(int i = 1 ; i <= n ; i++) { if(dp[i][m] > ans) { ans = dp[i][m]; id = i; } } cout << ans << '\n'; while(m > 0) { cout << id << " "; id = trace[id][m]; // st.push(n); m--; } // while(!st.empty()) { // cout << st.top() << " "; // st.pop(); // } return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:57:12: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         id = trace[id][m];
      |         ~~~^~~~~~~~~~~~~~
#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...