제출 #1103073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103073		aaaaaarroz	Nile (IOI24_nile)	C++17	67 / 100	2057 ms	6600 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
typedef long long ll;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {                   
  int Q = (int)E.size();
  int N=(int)W.size();
  vector<ll>ans;
  vector<tuple<int,int,int>>ordenar;
  for(int i=0;i<N;i++){
    ordenar.push_back({W[i],B[i],A[i]});
  }
  sort(ordenar.begin(),ordenar.end());
  W.clear();
  A.clear();
  B.clear();
  for(auto[w,b,a]:ordenar){
    A.push_back(a);
    B.push_back(b);
    W.push_back(w);
  }
  for(int e=0;e<Q;e++){
    int d=E[e];
    vector<ll>dp(N,LLONG_MAX);
    for(int i=0;i<N;i++){
      if(i==0){
        dp[i]=A[i];
      }
      if(i==1){
        if((W[i]-W[i-1])<=d){
          dp[i]=(B[i]+B[i-1]);
        }
        else{
          dp[i]=(dp[i-1]+A[i]);
        }
      }
      if(i>=2){
        dp[i]=((ll)A[i]+dp[i-1]);
        if((W[i]-W[i-1])<=d){
          dp[i]=min(dp[i],(ll)((ll)B[i]+(ll)B[i-1]+dp[i-2]));
        }
        if((W[i]-W[i-2])<=d){
          if(i>=3){
            dp[i]=min(dp[i],(ll)((ll)B[i]+(ll)B[i-2]+(ll)A[i-1]+dp[i-3]));
          }
          else{
            dp[i]=min(dp[i],(ll)((ll)B[i]+(ll)B[i-2]+(ll)A[i-1]));
          }
        }
      }
    }
    ans.push_back(dp[N-1]);
  }
  return ans;
}

• 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