Untitled
unknown
plain_text
2 years ago
4.2 kB
7
Indexable
fork download
#include <iostream>
using namespace std;
int T, N, arr[15], res[15], maxRes;
void backtracking(int index, int size, int sum) {
if (size == 0) {
maxRes = maxRes > sum ? maxRes : sum;
return;
}
// Ban
int number1 = -1, number2 = -1;
if(index - 1 >= 0) number1 = res[index - 1];
if(index + 1 < size) number2 = res[index + 1];
int tmp = res[index];
for(int i = index; i < size; i++) {
res[i] = res[i+1];
}
if(number1 != -1 && number2 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + (number1 * number2));
}
} else {
if(number1 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + number1);
}
} else if(number2 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + number2);
}
} else {
backtracking(index, size-1, sum + res[index]);
}
}
for(int i = size - 1; i > index; i--) {
res[i] = res[i-1];
}
res[index] = tmp;
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
//
maxRes = -1;
for(int i = 1; i < N-1; i++) {
// update new array
for(int j = 0; j < N; j++) {
res[j] = arr[j];
}
// backtrack
backtracking(i, N, 0);
}
cout << "#" << t << " " << maxRes << endl;
}
return 0;
}
Success #stdin #stdout 0.01s 5280KB
comments (0)
stdin
5 6 24 41 22 97 39 41 5 84 39 33 59 81 6 99 84 56 68 76 99 8 89 32 42 44 83 38 24 67 8 27 92 81 90 74 88 53 90
stdout
#1 11348 #2 14700 #3 30759 #4 29289 #5 43110
https://ideone.com/db0t8w
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
secret
Share or Embed source code
Discover > Sphere Engine API
The brand new service which powers Ideone!
Discover > IDE Widget
Widget for compiling and running the source code in a web browser!
Powered by Sphere Engine™
home api language faq credits
desktop mobile
terms of service privacy policy gdpr info
Feedback & Bugs
popular languages:
bash pascal c perl c# php c++ python c++14 python3 haskell ruby java sqlite objective-c swift vb.net
list of all supported programming languages
fork download
#include <iostream>
using namespace std;
int T, N, arr[15], res[15], maxRes;
void backtracking(int index, int size, int sum) {
if (size == 0) {
maxRes = maxRes > sum ? maxRes : sum;
return;
}
// Ban
int number1 = -1, number2 = -1;
if(index - 1 >= 0) number1 = res[index - 1];
if(index + 1 < size) number2 = res[index + 1];
int tmp = res[index];
for(int i = index; i < size; i++) {
res[i] = res[i+1];
}
if(number1 != -1 && number2 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + (number1 * number2));
}
} else {
if(number1 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + number1);
}
} else if(number2 != -1) {
for(int k = 0; k < size; k++) {
backtracking(k, size-1, sum + number2);
}
} else {
backtracking(index, size-1, sum + res[index]);
}
}
for(int i = size - 1; i > index; i--) {
res[i] = res[i-1];
}
res[index] = tmp;
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
//
maxRes = -1;
for(int i = 1; i < N-1; i++) {
// update new array
for(int j = 0; j < N; j++) {
res[j] = arr[j];
}
// backtrack
backtracking(i, N, 0);
}
cout << "#" << t << " " << maxRes << endl;
}
return 0;
}
Success #stdin #stdout 0.01s 5280KB
comments (0)
stdin
5 6 24 41 22 97 39 41 5 84 39 33 59 81 6 99 84 56 68 76 99 8 89 32 42 44 83 38 24 67 8 27 92 81 90 74 88 53 90
stdout
#1 11348 #2 14700 #3 30759 #4 29289 #5 43110
https://ideone.com/db0t8w
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
secret
Share or Embed source code
Discover > Sphere Engine API
The brand new service which powers Ideone!
Discover > IDE Widget
Widget for compiling and running the source code in a web browser!
Powered by Sphere Engine™
home api
Editor is loading...
Leave a Comment