제출 #693695

#제출 시각아이디문제언어결과실행 시간메모리
693695MurotY수열 (APIO14_sequence)C++14
0 / 100
25 ms27528 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define ull unsigned long long #define ff first #define ss second #define all(a) a.begin(), a.end() #define sz size() using namespace std; const ll N=1e6+7, M=1e9+7; ll a[N]; int pos[N]; ll memo[1005][205]; void solve() { int n, k; cin >> n >> k; ll sum=0; for (int i=1;i<=n;i++) cin >> a[i], sum+=a[i]; if (k == 0){ cout << sum; return ; } auto dp = [&] (auto& dp, int i, int k, ll sum) -> ll { vector <int> vc; vc.clear(); if (k <= 0 || i >= n+1) { return 0; } if (memo[i][k] != -1) return memo[i][k]; ll cur=0, ans=0; for (int j=i;j<=n;j++){ sum-=a[j], cur+=a[j]; ll res=dp(dp, j+1, k-1, sum); if (ans < sum*cur+res){ ans=sum*cur+res; pos[i]=j; } } memo[i][k]=ans; return ans; }; for (int i=0;i<=n;i++){ for (int j=0;j<=k;j++) memo[i][j]=-1; } ll res=dp(dp, 1, k, sum); // for (int i=1;i<=n;i++) cout << pos[i] <<" "; cout << res <<"\n"; int tmp=pos[1], cnt=0, ccc=0; while (cnt < k){ cout << tmp <<" "; tmp=pos[tmp+1]; cnt++; } return ; } int main(){ ios; int t=1; // cin >> t; while (t--){ solve(); cout << "\n"; } return 0; }

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

sequence.cpp: In function 'void solve()':
sequence.cpp:56:25: warning: unused variable 'ccc' [-Wunused-variable]
   56 |  int tmp=pos[1], cnt=0, ccc=0;
      |                         ^~~
#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...