제출 #1306853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306853		michael12	나일강 (IOI24_nile)	C++20	17 / 100	2095 ms	4652 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;

vector<long long> calculate_costs(
    vector<int> W,
    vector<int> A,
    vector<int> B,
    vector<int> E
) {
    int N = W.size();
    int Q = E.size();
    int t = 0;
    for(int i = 0; i < N; i++){
        if(A[i] != 2 || B[i] != 1){
           t++;
        }
    }
    if(t == 0){
        vector<long long> ss(Q);
        vector<long long> dif(N - 1);
        for(int i = 0; i < N - 1; i++){
            dif[i] = W[i + 1] - W[i];
        }
        sort(dif.begin(), dif.end());
        vector<long long> rs(Q);
        for(int i = 0; i < Q; i++){
            for(int j = 0; j < N; j++){
                int idx = upper_bound(W.begin(), W.end(), E[i] - W[j]) - W.begin();
                if(idx < N){
                    ss[i]++;
                    W[idx] = 0;
                }
            }
        }
        return ss;
    }
    else{

    vector<array<int,3>> at(N);
    for (int i = 0; i < N; i++) {
        at[i] = {W[i], A[i], B[i]};
    }

    sort(at.begin(), at.end());

    long long sm = 0;
    for (int i = 0; i < N; i++) {
        sm += at[i][1];
    }

    vector<long long> rs(Q);

    for (int qi = 0; qi < Q; qi++) {
        int D = E[qi];
        vector<long long> dp(N, 0);

        for (int i = 0; i < N; i++) {
            if (i > 0) dp[i] = dp[i - 1];

            for (int j = i - 1; j >= 0; j--) {
                if (at[i][0] - at[j][0] > D) break;

                long long sv =
                    (long long)at[i][1] + at[j][1]
                    - at[i][2] - at[j][2];

                if (j > 0)
                    dp[i] = max(dp[i], dp[j - 1] + sv);
                else
                    dp[i] = max(dp[i], sv);
            }
        }

        rs[qi] = sm - dp[N - 1];
    }

    return rs;
    }
}

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