Submission #1101502

#TimeUsernameProblemLanguageResultExecution timeMemory
1101502MThanCCVAK blocks (IZhO14_blocks)C++14
0 / 100
2 ms4492 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int MAXN = 1e4 + 5; int n, k; int dp[MAXN][105], a[MAXN]; int main() { freopen("blocks.inp", "r", stdin); freopen("blocks.out", "w", stdout); cin >> n >> k; memset(dp, 0x3f, sizeof(dp)); int mx = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; mx = max(mx, a[i]); dp[i][1] = mx; } for (int j = 2; j <= k; j++) { stack<pii> s; for (int i = 1; i <= n; i++) { int tmp = dp[i - 1][j - 1]; while (!s.empty() && s.top().first < a[i]) { tmp = min(tmp, s.top().second); s.pop(); } if (s.empty() || a[i] + tmp < s.top().first + s.top().second) s.push({a[i], tmp}); if (i >= j) dp[i][j] = s.top().first + s.top().second; } } cout << dp[n][k]; return 0; }

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:10:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |    freopen("blocks.inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:11:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |    freopen("blocks.out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...