oj.uz

Submission #101309

# Submission time Handle Problem Language Result Execution time Memory
101309 2019-03-18T12:02:24 Z b2563125 Candies (JOI18_candies) C++14
8 / 100
 514 ms 525312 KB 
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<int>
#define vvel vector<vel>
#define vvvel vector<vvel>
#define veb vector<bool>
void mmax(int &a, int b) { a = max(a, b); }
vel com(vel &u, vel &v) {
	vel ans(1,0);
	int mu = 0; int mv = 0;
	int su = u.size();
	int sv = v.size();
	while (mu < su - 1 or mv < sv - 1) {
		int nu = mu + 1;
		int nv = mv + 1;
		if (nu == su) { mv++; }
		else if (nv == sv) { mu++; }
		else if (u[nu] - u[mu] > v[nv] - v[mv]) { mu++; }
		else { mv++; }
		ans.push_back(u[mu] + v[mv]);
	}
	return ans;
}
vel r_no(int st, int to, vel &a) {
	int siz = to - st;
	int ko = (siz + 3) / 2;
	vvel dp(siz+1, vel(ko, -1));
	dp[0][0] = 0;
	dp[1][0] = 0; dp[1][1] = a[st];
	for (int i = 2; i <= siz; i++) {
		dp[i] = dp[i - 1];
		for (int j = 1; j < ko; j++) {
			if (dp[i - 2][j - 1] != -1) { mmax(dp[i][j], dp[i - 2][j - 1] + a[st + i - 1]); }
		}
	}
	return dp[siz];
}
signed main() {
	int n; cin >> n;
	vel a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	int ko = (n + 3) / 2;
	vel ans(ko);
	if (n > 2000) { ans = r_no(0, n, a); }
	else {
		int range = 500;
		vel dp0 = r_no(0, range, a);
		vel dp1 = r_no(0, range - 1, a);
		int st1 = 0;
		for (int i = 2; i*range <= n - range; i++) {
			int st = (i - 1)*range;
			int to = i * range; mmax(st1, to);
			vel x0 = r_no(st, to, a);
			vel x1 = r_no(st + 1, to, a);
			vel qdp0 = com(dp1, x0); x0.clear();
			vel rdp0 = com(dp0, x1); x1.clear();
			vel y0 = r_no(st, to - 1, a);
			vel y1 = r_no(st + 1, to - 1, a);
			vel qdp1 = com(dp1, y0); y0.clear();
			vel rdp1 = com(dp0, y1); y1.clear();
			dp0 = vel(0);
			for (int i = 0; i<qdp0.size() ; i++) { dp0.push_back(max(qdp0[i], rdp0[i]));}
			dp1 = vel(0);
			for (int i = 0; i < rdp1.size(); i++) { dp1.push_back(max(qdp1[i], rdp1[i])); }
			dp1.push_back(qdp1[qdp1.size() - 1]);
		}
		vel x = r_no(st1, n, a);
		vel y = r_no(st1 + 1, n, a);
		vel qans = com(dp0, y);
		vel rans = com(dp1, x);
		for (int i = 0; i < ko; i++) { ans[i] = max(qans[i], rans[i]); }
	}
	for (int i = 1; i < ko; i++) { cout << ans[i] << endl; }
	return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i<qdp0.size() ; i++) { dp0.push_back(max(qdp0[i], rdp0[i]));}
                    ~^~~~~~~~~~~~
candies.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < rdp1.size(); i++) { dp1.push_back(max(qdp1[i], rdp1[i])); }
                    ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1432 KB Output is correct
2 Correct 13 ms 1384 KB Output is correct
3 Correct 16 ms 1384 KB Output is correct
4 Correct 12 ms 1432 KB Output is correct
5 Correct 15 ms 1432 KB Output is correct
6 Correct 14 ms 1468 KB Output is correct
7 Correct 14 ms 1452 KB Output is correct
8 Correct 13 ms 1468 KB Output is correct
9 Correct 15 ms 1384 KB Output is correct
10 Correct 16 ms 1468 KB Output is correct
11 Correct 22 ms 4316 KB Output is correct
12 Correct 21 ms 4316 KB Output is correct
13 Correct 21 ms 4316 KB Output is correct
14 Correct 17 ms 4392 KB Output is correct
15 Correct 18 ms 4324 KB Output is correct
16 Correct 17 ms 4292 KB Output is correct
17 Correct 14 ms 4316 KB Output is correct
18 Correct 16 ms 4316 KB Output is correct
19 Correct 19 ms 4312 KB Output is correct
20 Correct 17 ms 4316 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1432 KB Output is correct
2 Correct 13 ms 1384 KB Output is correct
3 Correct 16 ms 1384 KB Output is correct
4 Correct 12 ms 1432 KB Output is correct
5 Correct 15 ms 1432 KB Output is correct
6 Correct 14 ms 1468 KB Output is correct
7 Correct 14 ms 1452 KB Output is correct
8 Correct 13 ms 1468 KB Output is correct
9 Correct 15 ms 1384 KB Output is correct
10 Correct 16 ms 1468 KB Output is correct
11 Correct 22 ms 4316 KB Output is correct
12 Correct 21 ms 4316 KB Output is correct
13 Correct 21 ms 4316 KB Output is correct
14 Correct 17 ms 4392 KB Output is correct
15 Correct 18 ms 4324 KB Output is correct
16 Correct 17 ms 4292 KB Output is correct
17 Correct 14 ms 4316 KB Output is correct
18 Correct 16 ms 4316 KB Output is correct
19 Correct 19 ms 4312 KB Output is correct
20 Correct 17 ms 4316 KB Output is correct
21 Runtime error 514 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -