제출 #29696

#제출 시각아이디문제언어결과실행 시간메모리
29696sampriti수열 (APIO14_sequence)C++14
0 / 100
2000 ms25960 KiB
#include <cstdio> #include <algorithm> #include <climits> using namespace std; int N, K; int A[100000]; long long P[100000]; long long dp[10001][202]; int nxt[10001][202]; long long query(int i, int j) { if(i > j) return 0; if(i == 0) return P[j]; return P[j] - P[i - 1]; } int main() { scanf("%d %d", &N, &K); for(int i = 0; i < N; i++) scanf("%d", &A[i]); P[0] = A[0]; for(int i = 1; i < N; i++) P[i] = P[i - 1] + A[i]; for(int i = 0; i < N; i++) dp[i][0] = LLONG_MIN/2; dp[N][0] = 0; for(int j = 1; j <= K + 1; j++) { dp[N][j] = LLONG_MIN/2; for(int i = N - 1; i >= 0; i--) { dp[i][j] = LLONG_MIN/2; for(int k = i; k < N; k++) { long long curr = query(i, k) * query(k + 1, N - 1) + dp[k + 1][j - 1]; if(curr > dp[i][j]) { dp[i][j] = curr; nxt[i][j] = k; } } } } printf("%lld\n", dp[0][K + 1]); int i = 0, j = K + 1; while(i < N) { printf("%d ", nxt[i][j] + 1); j--; i = nxt[i][j] + 1; } printf("\n"); }

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

sequence.cpp: In function 'int main()':
sequence.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &K);
                         ^
sequence.cpp:21:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; i < N; i++) scanf("%d", &A[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...