Submission #166638

#TimeUsernameProblemLanguageResultExecution timeMemory
166638abilK blocks (IZhO14_blocks)C++14
100 / 100
237 ms40828 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mk make_pair #define all(s) s.begin(),s.end() //#define int long long using namespace std; const int N = (1e5 + 12); const int mod = (1e9 + 7); const int INF = (0x3f3f3f3f); int a[N], dp[112][N], n; main() { int k; scanf("%d%d", &n, &k); for(int i = 1;i <= n; i++){ scanf("%d", &a[i]); } for(int i = 1;i <= n; i++){ dp[1][i] = max(dp[1][i - 1], a[i]); } for(int i = 2;i <= k; i++){ stack<pair<int,int > > st; dp[i][i] = dp[i - 1][i - 1] + a[i]; st.push({dp[i - 1][i - 1],a[i]}); for(int j = i + 1;j <= n; j++){ int c = dp[i - 1][j - 1]; while(!st.empty() && st.top().sc <= a[j]){ c = min(c, st.top().fr); st.pop(); } if(st.empty() || st.top().fr + st.top().sc > c + a[j]){ st.push({c, a[j]}); } dp[i][j] = st.top().fr + st.top().sc; } } cout << dp[k][n]; }

Compilation message (stderr)

blocks.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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...