제출 #367232

#제출 시각아이디문제언어결과실행 시간메모리
367232parsabahrami수열 (APIO14_sequence)C++17
0 / 100
18 ms24044 KiB
// Call my Name and Save me from The Dark #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 10000 + 10, K = 200; ll PS[N], S[N], dp[K][N]; int opt[K][N], A[N], n, k; ll get(int l, int r) { return S[r] - S[max(0, l - 1)] - (PS[r] - PS[max(0, l - 1)]) * PS[max(0, l - 1)]; } void DC(int j, int l = 1, int r = n, int optl = 1, int optr = n) { if (r - l < 0) return; int mid = (l + r) >> 1; for (int i = optl; i <= min(mid, optr); i++) { if (get(i, mid) + dp[j - 1][i - 1] < dp[j][mid]) { dp[j][mid] = get(i, mid) + dp[j - 1][i - 1], opt[j][mid] = i; } } if (~opt[j][mid]) DC(j, l, mid - 1, optl, opt[j][mid]); DC(j, mid + 1, r, max(1, opt[j][mid]), optr); } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &A[i]), PS[i] = PS[i - 1] + A[i]; for (int i = 1; i <= n; i++) { S[i] = S[i - 1] + 1ll * A[i] * PS[i - 1]; } memset(opt, -1, sizeof opt); for (int i = 0; i < K; i++) fill(dp[i], dp[i] + N, 1e16); for (int i = 0; i <= n; i++) dp[1][i] = S[i]; for (int i = 2; i <= k + 1; i++) { DC(i); } printf("%lld\n", S[n] - dp[k + 1][n]); int id = n; vector<int> vec; for (int i = k + 1; i > 1; i--) { if (opt[i][id] == -1) { printf("rid %d %d\n", i, id); break; } vec.push_back(opt[i][id]); id = opt[i][id] - 1; } reverse(vec.begin(), vec.end()); for (int &i : vec) printf("%d ", i); printf("\n"); return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:34:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     for (int i = 1; i <= n; i++) scanf("%d", &A[i]), PS[i] = PS[i - 1] + 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...