Submission #221863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
221863	2020-04-11T10:42:07 Z	patrikpavic2	Candies (JOI18_candies)	C++17	8 / 100	1010 ms	167440 KB

candies

#include <cstdio>
#include <vector>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef vector < ll > vi;

const int N = 3e5 + 500;

vi v[N][4];
int cnt = 0, n, A[N];

vi mrg(vi &A, vi &B){
	if(!A.size()) return B;
	if(!B.size()) return A;
	vi C = {A[0], B[0]};
	for(int i = 1;i < (int)A.size();i++)
		C.PB(A[i] - A[i - 1]);
	for(int i = 1;i < (int)B.size();i++)
		C.PB(B[i] - B[i - 1]);
	sort(C.rbegin(), C.rend());
	for(int i = 1;i < (int)C.size();i++)
		C[i] += C[i - 1];
	return C;
}

vi mks(vi A, vi B){
	if(A.size() < B.size()) swap(A, B);
	vi C = A;
	for(int i = 0;i < (int)B.size();i++)
		C[i] = max(C[i], B[i]);
	return C;
}

int solve(int l,int r){
	if(l == r){
		v[cnt][3].PB(A[l]);
		return cnt++;
	}
	int L = solve(l, (l + r) / 2);
	int R = solve((l + r) / 2 + 1, r);
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 4;j++){
			if((i&2) && (j&1)) continue;
			v[cnt][(i&1) + (j&2)] = mks(v[cnt][(i&1) + (j&2)], mrg(v[L][i], v[R][j]));
		}
	}
	return cnt++;	
}


int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++)
		scanf("%d", A + i); 
	int kraj = solve(0, n - 1);
	vi fin = mks(mks(v[kraj][0], v[kraj][1]), mks(v[kraj][2], v[kraj][3]));
	for(ll x : fin) printf("%lld\n", x);
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
candies.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i); 
   ~~~~~^~~~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	29184 KB	Output is correct
2	Correct	29 ms	29184 KB	Output is correct
3	Correct	31 ms	29176 KB	Output is correct
4	Correct	28 ms	29184 KB	Output is correct
5	Correct	28 ms	29184 KB	Output is correct
6	Correct	29 ms	29184 KB	Output is correct
7	Correct	29 ms	29184 KB	Output is correct
8	Correct	28 ms	29184 KB	Output is correct
9	Correct	28 ms	29184 KB	Output is correct
10	Correct	28 ms	29184 KB	Output is correct
11	Correct	31 ms	29184 KB	Output is correct
12	Correct	29 ms	29176 KB	Output is correct
13	Correct	29 ms	29184 KB	Output is correct
14	Correct	27 ms	29184 KB	Output is correct
15	Correct	28 ms	29184 KB	Output is correct
16	Correct	28 ms	29184 KB	Output is correct
17	Correct	29 ms	29184 KB	Output is correct
18	Correct	28 ms	29176 KB	Output is correct
19	Correct	29 ms	29184 KB	Output is correct
20	Correct	28 ms	29184 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	29184 KB	Output is correct
2	Correct	29 ms	29184 KB	Output is correct
3	Correct	31 ms	29176 KB	Output is correct
4	Correct	28 ms	29184 KB	Output is correct
5	Correct	28 ms	29184 KB	Output is correct
6	Correct	29 ms	29184 KB	Output is correct
7	Correct	29 ms	29184 KB	Output is correct
8	Correct	28 ms	29184 KB	Output is correct
9	Correct	28 ms	29184 KB	Output is correct
10	Correct	28 ms	29184 KB	Output is correct
11	Correct	31 ms	29184 KB	Output is correct
12	Correct	29 ms	29176 KB	Output is correct
13	Correct	29 ms	29184 KB	Output is correct
14	Correct	27 ms	29184 KB	Output is correct
15	Correct	28 ms	29184 KB	Output is correct
16	Correct	28 ms	29184 KB	Output is correct
17	Correct	29 ms	29184 KB	Output is correct
18	Correct	28 ms	29176 KB	Output is correct
19	Correct	29 ms	29184 KB	Output is correct
20	Correct	28 ms	29184 KB	Output is correct
21	Runtime error	1010 ms	167440 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-