oj.uz

Submission #101310

# Submission time Handle Problem Language Result Execution time Memory
101310 2019-03-18T12:04:28 Z b2563125 Candies (JOI18_candies) C++14
8 / 100
 528 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;
	if (n > 2000) { 
		vel x = r_no(0, n, a);
		for (int i = 0; i < x.size(); i++) { cout << x[i] << endl; }
	}
	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 = 1; i < ko; i++) { cout << max(qans[i], rans[i]) << endl; }
	}
	return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < x.size(); i++) { cout << x[i] << endl; }
                   ~~^~~~~~~~~~
candies.cpp:71: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:73: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 13 ms 1432 KB Output is correct
2 Correct 14 ms 1468 KB Output is correct
3 Correct 12 ms 1432 KB Output is correct
4 Correct 13 ms 1468 KB Output is correct
5 Correct 12 ms 1468 KB Output is correct
6 Correct 12 ms 1468 KB Output is correct
7 Correct 12 ms 1432 KB Output is correct
8 Correct 15 ms 1432 KB Output is correct
9 Correct 18 ms 1416 KB Output is correct
10 Correct 13 ms 1384 KB Output is correct
11 Correct 15 ms 4316 KB Output is correct
12 Correct 17 ms 4316 KB Output is correct
13 Correct 17 ms 4316 KB Output is correct
14 Correct 14 ms 4316 KB Output is correct
15 Correct 22 ms 4316 KB Output is correct
16 Correct 16 ms 4316 KB Output is correct
17 Correct 16 ms 4392 KB Output is correct
18 Correct 18 ms 4392 KB Output is correct
19 Correct 16 ms 4316 KB Output is correct
20 Correct 15 ms 4316 KB Output is correct

Subtask #2
0 / 92.0

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