제출 #47515

#제출 시각아이디문제언어결과실행 시간메모리
47515Waschbar수열 (APIO14_sequence)C++17
50 / 100
2066 ms14080 KiB
///©Waschbar #include <bits/stdc++.h> #define tmm first #define uu second.first #define vv second.second using namespace std; const int MAXN = 10000; const int LOG = 20; const long long INF = 1e15; const int MOD = 1e9+7; long long n, m; long long val[MAXN+1], sum[MAXN+1]; long long dp[201][MAXN+1]; long long p[201][MAXN+1]; vector < long long > v; void func(long long k, long long j) { if(k == 0ll) return; v.push_back(p[k][j]); func(k-1,p[k][j]); } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> val[i]; sum[i] = sum[i-1] + val[i]; } for(int j = 1; j <= n; j++) for(int i = 1; i <= m; i++) { dp[i][j] = -1; for(int k = 1; k < j; k++){ long long x = dp[i-1][k]+(sum[j]-sum[k])*sum[k]; if(dp[i-1][k] == -1) continue; if(x > dp[i][j]) { dp[i][j] = x; p[i][j] = k; //cout << i << " " << j << " " << k << endl; } } } cout << dp[m][n] << endl; func(m,n); for(int i = 0; i < v.size(); i++) cout << v[i] << " "; return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++)
                    ~~^~~~~~~~~~
#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...