oj.uz

답안 #489665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489665 2021-11-23T18:16:46 Z Alexandruabcde Salesman (IOI09_salesman) C++14
60 / 100
 365 ms 39608 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11980 KB Output is correct
2 Correct 6 ms 12060 KB Output is correct
3 Correct 8 ms 12072 KB Output is correct
4 Correct 10 ms 12108 KB Output is correct
5 Correct 8 ms 12340 KB Output is correct
6 Correct 28 ms 16952 KB Output is correct
7 Correct 43 ms 18408 KB Output is correct
8 Correct 87 ms 20788 KB Output is correct
9 Correct 95 ms 22916 KB Output is correct
10 Correct 188 ms 30080 KB Output is correct
11 Correct 222 ms 30720 KB Output is correct
12 Correct 286 ms 34604 KB Output is correct
13 Correct 271 ms 34880 KB Output is correct
14 Correct 365 ms 39608 KB Output is correct
15 Correct 302 ms 39472 KB Output is correct
16 Correct 330 ms 39492 KB Output is correct
17 Incorrect 7 ms 11980 KB Output isn't correct
18 Incorrect 6 ms 12004 KB Output isn't correct
19 Incorrect 7 ms 12108 KB Output isn't correct
20 Incorrect 7 ms 12108 KB Output isn't correct
21 Incorrect 6 ms 12076 KB Output isn't correct
22 Incorrect 8 ms 12164 KB Output isn't correct
23 Incorrect 8 ms 12236 KB Output isn't correct
24 Incorrect 11 ms 12208 KB Output isn't correct
25 Incorrect 45 ms 18408 KB Output isn't correct
26 Incorrect 81 ms 21044 KB Output isn't correct
27 Incorrect 123 ms 24336 KB Output isn't correct
28 Incorrect 144 ms 25460 KB Output isn't correct
29 Incorrect 178 ms 27376 KB Output isn't correct
30 Incorrect 188 ms 28956 KB Output isn't correct