Submission #1210456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210456		PagodePaiva	Nile (IOI24_nile)	C++20	67 / 100	2092 ms	10148 KiB

nile

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

using namespace std;

const int N = 200010;
long long dp[N];
long long custo[N];
long long w[N];

vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
    int n = W.size();
    long long sum = 0;
    vector <array <int, 3>> ordenar;
    for(int i = 0;i < n;i++){
        ordenar.push_back({W[i], A[i], B[i]});
    }
    sort(ordenar.begin(), ordenar.end());
    for(int i = 0;i < n;i++){
        w[i+1] = ordenar[i][0];
        sum += (long long) (ordenar[i][1]);
        custo[i+1] = ordenar[i][1] - ordenar[i][2];
    }
    vector <long long> resposta;
    for(auto d : E){
        long long res = 0;
        vector <pair <long long, long long>> intervalos;
        intervalos.push_back({w[1], custo[1]});
        for(int i = 2;i <= n;i++){
            if(w[i] - w[i-1] > d){
                long long soma = intervalos[0].second;
                long long mn = intervalos[0].second;
                int tam = intervalos.size();
                for(int j = 1;j < intervalos.size();j++){
                    soma += intervalos[j].second;
                    if(j%2 == 0){
                        mn = min(mn, intervalos[j].second);
                    }
                    else if(j+1 != tam){
                        if(intervalos[j+1].first - intervalos[j-1].first <= d){
                            mn = min(mn, intervalos[j].second);
                        }
                    }
                }
                res += soma - (tam%2 == 1 ? mn : 0);
                intervalos.clear();
                intervalos.push_back({w[i], custo[i]});
            }
            else{
                intervalos.push_back({w[i], custo[i]});
            }
        }
        long long soma = intervalos[0].second;
        long long mn = intervalos[0].second;
        int tam = intervalos.size();
        for(int j = 1;j < intervalos.size();j++){
            soma += intervalos[j].second;
            if(j%2 == 0){
                mn = min(mn, intervalos[j].second);
            }
            else if(j+1 != tam){
                if(intervalos[j+1].first - intervalos[j-1].first <= d){
                    mn = min(mn, intervalos[j].second);
                }
            }
        }
        res += soma - (tam%2 == 1 ? mn : 0);
        resposta.push_back(sum-res);
    }
    return resposta;
}

• 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