제출 #1273525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273525		mkkkkkkkk	나일강 (IOI24_nile)	C++20	67 / 100	2094 ms	5788 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>


using namespace std;

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E)
{
  vector<pair<long long,long long>> vec;
  for(long long i=0;i<W.size();i++)
  {
      vec.push_back({W[i],A[i]-B[i]});
  }
  sort(vec.begin(),vec.end());
  long long sum=0;
  for(auto it : A)
    sum+=it;
  vector<long long> res;
  for(auto it : E)
  {
      long long D=it;
    long long dp[W.size()]={};
      dp[0]=0;
      for(long long i=1;i<vec.size();i++)
      {
          dp[i]=dp[i-1];
          if(vec[i].first-vec[i-1].first<=D)
          {
              if(i==1)
              {
                  dp[i]=max(vec[i].second+vec[i-1].second,dp[i]);
              }
              else
              dp[i]=max(dp[i],vec[i].second+vec[i-1].second+dp[i-2]);

              if(i>=2 && vec[i].first-vec[i-2].first<=D)
              {
                    if(i==2)
                  {
                      dp[i]=max(vec[i].second+vec[i-2].second,dp[i]);
                  }
                  else
                  dp[i]=max(dp[i],vec[i].second+vec[i-2].second+dp[i-3]);
              }
          }
      }
        res.push_back(sum-dp[vec.size()-1]);
  }
  return res;

}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18