Submission #489665

#	Time	Username	Problem	Language	Result	Execution time	Memory
489665		Alexandruabcde	Salesman (IOI09_salesman)	C++14	60 / 100	365 ms	39608 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int LIMITA = 5e5 + 5;
constexpr int INF = 2000000000;

int Capat;
int TimeMax;

class FenwickTree {
private:
    int aib[LIMITA];
    int ub (int i) {
        return (i&(-i));
    }
public:
    void Init () {
        for (int i = 1; i <= Capat; ++ i )
            aib[i] = -INF;
    }
    void Update (int pos, int val) {
        for (int i = pos; i <= Capat; i += ub(i))
            aib[i] = max(aib[i], val);
    }
    int Query (int pos) {
        int Max = -INF;

        for (int i = pos; i > 0; i -= ub(i))
            Max = max(Max, aib[i]);

        return Max;
    }
};
FenwickTree St, Dr;

struct Fair {
    int locatie;
    int profit;
};
bool operator< (Fair a, Fair b) {
    return (a.locatie < b.locatie);
}

vector <Fair> V[LIMITA];

int ToLeft, ToRight, N, S;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> ToLeft >> ToRight >> S;
    Capat = S;
    for (int i = 1; i <= N; ++ i ) {
        int timp;
        Fair aux;
        cin >> timp >> aux.locatie >> aux.profit;
        Capat = max(Capat, aux.locatie);

        V[timp].push_back(aux);
        TimeMax = max(TimeMax, timp);
    }

    St.Init();
    Dr.Init();
}

int LR[LIMITA];
int RL[LIMITA];

void Solve () {
    Dr.Update(S, S * ToRight);
    St.Update(Capat - S + 1, -S * ToLeft);
    for (int i = 0; i <= TimeMax; ++ i ) {
        if (V[i].empty()) continue;

        sort(V[i].begin(), V[i].end());

        int ind = 0;
        for (auto it : V[i]) {
            int loc = it.locatie;
            int prof = it.profit;

            int Max_st = St.Query(Capat - loc + 1) + loc * ToLeft + prof;
            int Max_dr = Dr.Query(loc) - loc * ToRight + prof;

            RL[ind] = LR[ind] = max(Max_st, Max_dr);
        }

        for (int j = 1; j < V[i].size(); ++ j )
            LR[j] = max(LR[j], LR[j-1] - (V[i][j].locatie - V[i][j-1].locatie) * ToRight + V[i][j].profit);

        for (int j = V[i].size()-2; j >= 0; -- j )
            RL[j] = max(RL[j+1], RL[j+1] - (V[i][j+1].locatie - V[i][j].locatie) * ToLeft + V[i][j].profit);

        for (int j = 0; j < V[i].size(); ++ j ) {
            int loc = V[i][j].locatie;
            Dr.Update(loc, max(LR[j], RL[j]) + loc * ToRight);
            St.Update(Capat - loc + 1, max(LR[j], RL[j]) - ToLeft * loc);
        }
    }

    cout << max(Dr.Query(S) - S * ToRight, St.Query(Capat - S + 1) + S * ToLeft) << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void Solve()':
salesman.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j = 1; j < V[i].size(); ++ j )
      |                         ~~^~~~~~~~~~~~~
salesman.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Fair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int j = 0; j < V[i].size(); ++ j ) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 60 / 100