oj.uz

Submission #101308

# Submission time Handle Problem Language Result Execution time Memory
101308 2019-03-18T11:56:46 Z b2563125 Candies (JOI18_candies) C++14
8 / 100
 482 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 = vel(0);
			vel rdp0 = com(dp0, x1); x1 = vel(0);
			vel y0 = r_no(st, to - 1, a);
			vel y1 = r_no(st + 1, to - 1, a);
			vel qdp1 = com(dp1, y0); y0 = vel(0);
			vel rdp1 = com(dp0, y1); y1 = vel(0);
			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 1412 KB Output is correct
2 Correct 14 ms 1540 KB Output is correct
3 Correct 12 ms 1388 KB Output is correct
4 Correct 9 ms 1388 KB Output is correct
5 Correct 12 ms 1388 KB Output is correct
6 Correct 13 ms 1448 KB Output is correct
7 Correct 14 ms 1420 KB Output is correct
8 Correct 13 ms 1448 KB Output is correct
9 Correct 18 ms 1476 KB Output is correct
10 Correct 13 ms 1420 KB Output is correct
11 Correct 15 ms 4288 KB Output is correct
12 Correct 18 ms 4288 KB Output is correct
13 Correct 19 ms 4416 KB Output is correct
14 Correct 18 ms 4428 KB Output is correct
15 Correct 15 ms 4416 KB Output is correct
16 Correct 14 ms 4276 KB Output is correct
17 Correct 16 ms 4288 KB Output is correct
18 Correct 17 ms 4288 KB Output is correct
19 Correct 19 ms 4416 KB Output is correct
20 Correct 19 ms 4288 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1412 KB Output is correct
2 Correct 14 ms 1540 KB Output is correct
3 Correct 12 ms 1388 KB Output is correct
4 Correct 9 ms 1388 KB Output is correct
5 Correct 12 ms 1388 KB Output is correct
6 Correct 13 ms 1448 KB Output is correct
7 Correct 14 ms 1420 KB Output is correct
8 Correct 13 ms 1448 KB Output is correct
9 Correct 18 ms 1476 KB Output is correct
10 Correct 13 ms 1420 KB Output is correct
11 Correct 15 ms 4288 KB Output is correct
12 Correct 18 ms 4288 KB Output is correct
13 Correct 19 ms 4416 KB Output is correct
14 Correct 18 ms 4428 KB Output is correct
15 Correct 15 ms 4416 KB Output is correct
16 Correct 14 ms 4276 KB Output is correct
17 Correct 16 ms 4288 KB Output is correct
18 Correct 17 ms 4288 KB Output is correct
19 Correct 19 ms 4416 KB Output is correct
20 Correct 19 ms 4288 KB Output is correct
21 Runtime error 482 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -