/ SeriousOJ /

Record Detail

Runtime Error


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 832.0 KiB
#2 Accepted 3ms 1.02 MiB
#3 Accepted 2ms 1.066 MiB
#4 Accepted 2ms 1008.0 KiB
#5 Accepted 2ms 1.066 MiB
#6 Accepted 2ms 1.066 MiB
#7 Accepted 2ms 1.07 MiB
#8 Accepted 2ms 1.062 MiB
#9 Accepted 2ms 1.02 MiB
#10 Accepted 2ms 912.0 KiB
#11 Accepted 2ms 1.062 MiB
#12 Accepted 13ms 2.562 MiB
#13 Accepted 41ms 3.344 MiB
#14 Runtime Error 2ms 1.062 MiB
#15 Runtime Error 4ms 1.062 MiB
#16 Runtime Error 4ms 1.062 MiB
#17 Runtime Error 10ms 1.449 MiB
#18 Runtime Error 2ms 1.07 MiB
#19 Runtime Error 4ms 1.164 MiB
#20 Runtime Error 4ms 1.066 MiB
#21 Runtime Error 4ms 1.02 MiB
#22 Runtime Error 4ms 1.18 MiB
#23 Runtime Error 4ms 1.172 MiB
#24 Runtime Error 4ms 1.18 MiB
#25 Runtime Error 4ms 1.184 MiB
#26 Runtime Error 4ms 1.188 MiB
#27 Runtime Error 4ms 1.07 MiB
#28 Runtime Error 5ms 1.438 MiB
#29 Runtime Error 17ms 4.605 MiB
#30 Runtime Error 10ms 1.688 MiB
#31 Runtime Error 10ms 1.52 MiB
#32 Runtime Error 2ms 1.062 MiB
#33 Runtime Error 9ms 1.449 MiB
#34 Runtime Error 4ms 1.398 MiB
#35 Runtime Error 9ms 1.699 MiB

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 105;
const ll MOD = 1e9 + 7;

int n;
vector<vector<map<pair<int, int>, int>>> dp(N, vector<map<pair<int, int>, int>>(N));

int max_gcd(int ind, vector<int> &v, int gc, int gc2, int cnt) {
  if(ind == n) {
    if(cnt == (n + 1) / 2) {
      return gc + gc2;
    }
    return 0;
  }

  if (dp[ind][cnt].find({gc, gc2}) != dp[ind][cnt].end()) return dp[ind][cnt][{gc, gc2}];

  int take = max_gcd(ind + 1, v, gcd(gc, v[ind]), gc2, cnt + 1);
  int notTake = max_gcd(ind + 1, v, gc, gcd(gc2, v[ind]), cnt);

  return dp[ind][cnt][{gc, gc2}] = max(take, notTake);
}

void solve()
{
  cin >> n;
  
  vector<int> v(n);
  for(int i = 0; i < n; i++) {
    cin >> v[i];
  }
  
  cout << max_gcd(0, v, 0, 0, 0) << "\n";

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) dp[i][j].clear();
  }
}

int main()
{
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

  int t;
  cin >> t;
  while(t--){
    solve();
  }
}

Information

Submit By
Type
Submission
Problem
P1077 Even Odd GCD (Hard Version)
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-18 15:34:07
Judged At
2024-10-03 13:16:20
Judged By
Score
37
Total Time
41ms
Peak Memory
4.605 MiB