oj.uz

Submission #173981

# Submission time Handle Problem Language Result Execution time Memory
173981 2020-01-06T05:18:27 Z tourist K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 83708 KB 
#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()

using namespace std;

const int N = 1e5 + 5;

int n, k, a[N];

long long dp[N][105];

vector <pair<int, long long> > vec;

main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[0][0] = 0;
	for (int j = 1; j <= k; j++) {
		vec.clear();
		for (int i = 1; i <= n; i++) {
			long long mn = dp[i - 1][j - 1];
			while (!vec.empty() && vec.back().fr <= a[i]) {
				mn = min(mn, vec.back().sc);
				vec.pop_back();
			}
			vec.pb({a[i], mn});
			mn = 1e18;
			for (auto it : vec)
				mn = min(mn, it.fr + it.sc);
				
			dp[i][j] = mn;
		}
	}	
	cout << dp[n][k]<< endl;
}

Compilation message

blocks.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 82552 KB Output is correct
2 Correct 70 ms 82464 KB Output is correct
3 Correct 70 ms 82524 KB Output is correct
4 Correct 70 ms 82552 KB Output is correct
5 Correct 70 ms 82552 KB Output is correct
6 Correct 70 ms 82524 KB Output is correct
7 Correct 70 ms 82552 KB Output is correct
8 Correct 72 ms 82552 KB Output is correct
9 Correct 68 ms 82440 KB Output is correct
10 Correct 81 ms 82504 KB Output is correct
11 Correct 80 ms 82552 KB Output is correct
12 Correct 79 ms 82556 KB Output is correct
13 Correct 80 ms 82552 KB Output is correct
14 Correct 75 ms 82552 KB Output is correct
15 Correct 71 ms 82524 KB Output is correct
16 Correct 73 ms 82552 KB Output is correct
17 Correct 79 ms 82564 KB Output is correct
18 Correct 74 ms 82568 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 82568 KB Output is correct
2 Correct 70 ms 82552 KB Output is correct
3 Correct 80 ms 82556 KB Output is correct
4 Correct 71 ms 82476 KB Output is correct
5 Correct 80 ms 82552 KB Output is correct
6 Correct 73 ms 82552 KB Output is correct
7 Correct 73 ms 82552 KB Output is correct
8 Correct 77 ms 82520 KB Output is correct
9 Correct 71 ms 82552 KB Output is correct
10 Correct 70 ms 82552 KB Output is correct
11 Correct 79 ms 82552 KB Output is correct
12 Correct 78 ms 82680 KB Output is correct
13 Correct 70 ms 82552 KB Output is correct
14 Correct 70 ms 82680 KB Output is correct
15 Correct 70 ms 82552 KB Output is correct
16 Correct 70 ms 82524 KB Output is correct
17 Correct 70 ms 82552 KB Output is correct
18 Correct 70 ms 82512 KB Output is correct
19 Correct 70 ms 82552 KB Output is correct
20 Correct 70 ms 82552 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 82484 KB Output is correct
2 Correct 70 ms 82472 KB Output is correct
3 Correct 72 ms 82524 KB Output is correct
4 Correct 71 ms 82552 KB Output is correct
5 Correct 70 ms 82508 KB Output is correct
6 Correct 71 ms 82528 KB Output is correct
7 Correct 70 ms 82552 KB Output is correct
8 Correct 71 ms 82552 KB Output is correct
9 Correct 70 ms 82556 KB Output is correct
10 Correct 70 ms 82552 KB Output is correct
11 Correct 70 ms 82692 KB Output is correct
12 Correct 71 ms 82524 KB Output is correct
13 Correct 70 ms 82552 KB Output is correct
14 Correct 70 ms 82552 KB Output is correct
15 Correct 70 ms 82508 KB Output is correct
16 Correct 70 ms 82552 KB Output is correct
17 Correct 70 ms 82552 KB Output is correct
18 Correct 70 ms 82552 KB Output is correct
19 Correct 70 ms 82552 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 82652 KB Output is correct
2 Correct 88 ms 82944 KB Output is correct
3 Correct 94 ms 83188 KB Output is correct
4 Correct 189 ms 83064 KB Output is correct
5 Correct 442 ms 83636 KB Output is correct
6 Correct 95 ms 83704 KB Output is correct
7 Correct 241 ms 83576 KB Output is correct
8 Correct 70 ms 82524 KB Output is correct
9 Correct 70 ms 82552 KB Output is correct
10 Correct 70 ms 82552 KB Output is correct
11 Correct 70 ms 82552 KB Output is correct
12 Correct 70 ms 82520 KB Output is correct
13 Correct 70 ms 82552 KB Output is correct
14 Correct 113 ms 82680 KB Output is correct
15 Correct 73 ms 82680 KB Output is correct
16 Correct 83 ms 82680 KB Output is correct
17 Correct 80 ms 83016 KB Output is correct
18 Correct 103 ms 83092 KB Output is correct
19 Correct 225 ms 83192 KB Output is correct
20 Correct 618 ms 83708 KB Output is correct
21 Correct 105 ms 83576 KB Output is correct
22 Correct 327 ms 83704 KB Output is correct
23 Correct 90 ms 83704 KB Output is correct
24 Correct 144 ms 83576 KB Output is correct
25 Correct 739 ms 83580 KB Output is correct
26 Correct 71 ms 82552 KB Output is correct
27 Correct 73 ms 82552 KB Output is correct
28 Execution timed out 1085 ms 82680 KB Time limit exceeded
29 Halted 0 ms 0 KB -