oj.uz

Submission #148524

# Submission time Handle Problem Language Result Execution time Memory
148524 2019-09-01T04:36:02 Z 욱방켜!! (twitch.tv/wookje)(#3584, kig9981, cheetose, jh05013) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 177 ms 15688 KB 
#include "squad.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MX = 300002;

int N;
ll a[MX], d[MX], p[MX];
ll dpref[MX], dsuf[MX];
bool subtask2 = true;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = A.size();
	for(int i=0; i<N; i++){
		a[i] = A[i], d[i] = D[i], p[i] = P[i];
		if(d[i] != 1) subtask2 = false;
	}
}

long long BestSquad(int X, int Y){
	if(subtask2){
		;
		// todo...
	}

	for(int i=0; i<N; i++){
		a[i] = a[i]*X + p[i]*Y;
		d[i] = d[i]*X + p[i]*Y;
	}
	dpref[0] = d[0];
	for(int i=1; i<N; i++) dpref[i] = max(d[i], dpref[i-1]);
	dsuf[N-1] = d[N-1];
	for(int i=N-2; i>=0; i--) dsuf[i] = max(d[i], dsuf[i+1]);

	// pick i!=j to maximize a[i]+d[j]
	ll ans = -1;
	for(int i=0; i<N; i++){
		ll val = a[i];
		ll dmax = -1;
		if(i) dmax = max(dmax, dpref[i-1]);
		if(i != N-1) dmax = max(dmax, dsuf[i+1]);
		ans = max(ans, val+dmax);
	}
	return ans;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 173 ms 15676 KB Output is correct
4 Correct 172 ms 15688 KB Output is correct
5 Correct 17 ms 1560 KB Output is correct
6 Correct 177 ms 15676 KB Output is correct
7 Correct 169 ms 15676 KB Output is correct
8 Correct 173 ms 15676 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 173 ms 15676 KB Output is correct
4 Correct 172 ms 15688 KB Output is correct
5 Correct 17 ms 1560 KB Output is correct
6 Correct 177 ms 15676 KB Output is correct
7 Correct 169 ms 15676 KB Output is correct
8 Correct 173 ms 15676 KB Output is correct
9 Incorrect 6 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -