/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Wrong Answer 106ms 640.0 KiB
#3 Wrong Answer 87ms 552.0 KiB

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
  int t;
  cin >> t;
  while (t--){
    ll n, ans = 0;
    cin >> n;
    vector<ll> a(n + 10), vis(n + 10), dp(n + 10, 1e18);
    for (int i = 1; i <= n; i++){
      cin >> a[i];
    }
    dp[1] = 0, dp[2] = a[1], dp[3] = a[1] + a[2];
    for (int i = 1; i <= n; i++){
      dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
      dp[i + 2] = min(dp[i + 2], dp[i] + a[i] + a[i + 1]);
      dp[i + 3] = min(dp[i + 3], dp[i] + a[i + 1] + a[i + 2]);
    }
    ll j, mn = 1e18;
    for (int i = n + 1; i <= n + 3; i++){
      if (dp[i] < mn){
        mn = dp[i], j = i;
      }
    } //cout<<mn<<endl;
    ans += mn;
    mn = 1e18;
    for (int i = j; i > 0; i -= 3){
      vis[i] = 1, a[i] = 0;
    } //for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
    dp[2] = a[1], dp[3] = a[1] + a[2];
    for (int i = 4; i <= n + 3; i++) dp[i] = 1e18;
    for (int i = 1; i <= n; i++){
      dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
      dp[i + 2] = min(dp[i + 2], dp[i] + a[i] + a[i + 1]);
      dp[i + 3] = min(dp[i + 3], dp[i] + a[i + 1] + a[i + 2]);
    }
    for (int i = n + 1; i <= n + 3; i++){
      if (!vis[i] && dp[i] < mn){
        mn = dp[i];
      }
    } //cout<<mn<<endl;
    cout << ans + mn << endl;
  }
}

Information

Submit By
Type
Submission
Problem
P1087 Face the monsters
Contest
Brain Booster #5
Language
C++17 (G++ 13.2.0)
Submit At
2024-09-05 17:42:31
Judged At
2024-11-11 02:57:49
Judged By
Score
5
Total Time
106ms
Peak Memory
640.0 KiB