제출 #103562

#제출 시각아이디문제언어결과실행 시간메모리
103562kjain_1810수열 (APIO14_sequence)C++17
28 / 100
19 ms3584 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define s second #define ind(a) scanf("%d", &a) #define inlld(a) scanf("%lld", &a) #define ind2(a, b) scanf("%d%d", &a, &b) #define inlld2(a, b) scanf("%lld%lld", &a, &b) #define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c) using namespace std; const int N=1e3+5; const int MOD=1e9+7; typedef long long ll; typedef long double ld; ll arr[N], n, k, dp[N][205], pref[N], nex[N][205]; void solve(ll lev, ll l, ll r, ll optL, ll optR) { if(l>r) return; ll mid=(l+r)/2; for(ll a=optL; a<=optR && a<mid; a++) { ll here=dp[a][lev-1]+(pref[mid]-pref[a])*pref[a]; if(here>dp[mid][lev]) { dp[mid][lev]=here; nex[mid][lev]=a; } } solve(lev, l, mid-1, optL, nex[mid][lev]); solve(lev, mid+1, r, nex[mid][lev], optR); } int main() { inlld2(n, k); for(ll a=1; a<=n; a++) { inlld(arr[a]); pref[a]=pref[a-1]+arr[a]; } for(ll a=1; a<=n; a++) for(ll b=1; b<=k; b++) dp[a][b]=0; // for(ll b=1; b<=k; b++) // for(ll a=1; a<=n; a++) // { // for(ll c=1; c<a; c++) // { // if(dp[c][b-1]+(pref[a]-pref[c])*pref[c]>dp[a][b]) // { // dp[a][b]=dp[c][b-1]+(pref[a]-pref[c])*pref[c]; // nex[a][b]=c; // } // } // } for(ll a=1; a<=k; a++) solve(a, 1, n, 1, n); printf("%lld\n", dp[n][k]); ll i=n, j=k; vector<ll>ans; while(j>0) { ans.pb(nex[i][j]); i=nex[i][j]; j--; } for(ll a=ans.size()-1; a>=0; a--) printf("%lld ", ans[a]); printf("\n"); return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:8:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:42:5: note: in expansion of macro 'inlld2'
     inlld2(n, k);
     ^~~~~~
sequence.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld(a) scanf("%lld", &a)
                  ~~~~~^~~~~~~~~~~~
sequence.cpp:45:9: note: in expansion of macro 'inlld'
         inlld(arr[a]);
         ^~~~~
#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...