oj.uz

Submission #53510

# Submission time Handle Problem Language Result Execution time Memory
53510 2018-06-30T06:44:00 Z 강태규(#1417) Salesman (IOI09_salesman) C++11
80 / 100
 1000 ms 44600 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int MAXX = 5e5 + 1;
const llong inf = 1e16;
int n, u, d, s;
struct sale {
    int x, m;
    void scan() {
        scanf("%d%d", &x, &m);
    }
    bool operator<(const sale &p) const {
        return x < p.x;
    }
};
vector<sale> arr[MAXX + 2];
llong dpl[MAXX], dpr[MAXX], dp[MAXX];

llong segd[1 << 20];
llong segu[1 << 20];
void update(llong seg[], int i, int s, int e, int x, llong v) {
    if (s == e) {
        seg[i] = v;
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(seg, i << 1, s, m, x, v);
    else update(seg, i << 1 | 1, m + 1, e, x, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

llong query(llong seg[], int i, int s, int e, int x, int y) {
    if (e < x || y < s) return -inf;
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(query(seg, i << 1, s, m, x, y)
               , query(seg, i << 1 | 1, m + 1, e, x, y));
}

int main() {
    for (int i = 0; i < (1 << 20); ++i) segd[i] = segu[i] = -inf;
    scanf("%d%d%d%d", &n, &u, &d, &s);
    update(segu, 1, 1, MAXX, s, -u * s);
    update(segd, 1, 1, MAXX, s, d * s);
    for (int i = 0; i < n; ++i) {
        int t; sale s;
        scanf("%d", &t);
        s.scan();
        arr[t].push_back(s);
    }
    arr[MAXX + 1].push_back({ s, 0 });
    
    llong v;
    for (int it = 1; it <= MAXX + 1; ++it) {
        sort(arr[it].begin(), arr[it].end());
        int x, pr, m;
        for (int i = 0; i < arr[it].size(); ++i) {
            x = arr[it][i].x;
            m = arr[it][i].m;
            dp[i] = max(query(segu, 1, 1, MAXX, x, MAXX) + u * x + m
                     , query(segd, 1, 1, MAXX, 1, x) - d * x + m);
            dpr[i] = dp[i];
            if (i) dpr[i] = max(dpr[i], dpr[i - 1] - d * (x - pr) + m);
            pr = arr[it][i].x;
        }
        
        for (int i = arr[it].size(); i--; ) {
            x = arr[it][i].x;
            m = arr[it][i].m;
            dpl[i] = dp[i];
            if (i + 1 < arr[it].size())
                dpl[i] = max(dpl[i], dpl[i + 1] - u * (pr - x) + m);
            pr = arr[it][i].x;
        }
        
        for (int i = 0; i < arr[it].size(); ++i) {
            x = arr[it][i].x;
            m = arr[it][i].m;
            v = max(dpl[i], dpr[i]);
            update(segu, 1, 1, MAXX, x, v - u * x);
            update(segd, 1, 1, MAXX, x, v + d * x);
        }
    }
    
    printf("%lld\n", v);
	return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < arr[it].size(); ++i) {
                         ~~^~~~~~~~~~~~~~~~
salesman.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i + 1 < arr[it].size())
                 ~~~~~~^~~~~~~~~~~~~~~~
salesman.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < arr[it].size(); ++i) {
                         ~~^~~~~~~~~~~~~~~~
salesman.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
         ~~~~~^~~~~~~~~~
salesman.cpp: In member function 'void sale::scan()':
salesman.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &m);
         ~~~~~^~~~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:89:59: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 dpl[i] = max(dpl[i], dpl[i + 1] - u * (pr - x) + m);
                                                       ~~~~^~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28536 KB Output is correct
2 Correct 28 ms 28616 KB Output is correct
3 Correct 28 ms 28680 KB Output is correct
4 Correct 31 ms 28680 KB Output is correct
5 Correct 34 ms 28816 KB Output is correct
6 Correct 72 ms 29244 KB Output is correct
7 Correct 182 ms 30268 KB Output is correct
8 Correct 259 ms 31748 KB Output is correct
9 Correct 399 ms 33564 KB Output is correct
10 Correct 730 ms 38044 KB Output is correct
11 Correct 828 ms 38188 KB Output is correct
12 Correct 981 ms 41372 KB Output is correct
13 Execution timed out 1004 ms 41372 KB Time limit exceeded
14 Execution timed out 1094 ms 44340 KB Time limit exceeded
15 Execution timed out 1081 ms 44600 KB Time limit exceeded
16 Execution timed out 1072 ms 44600 KB Time limit exceeded
17 Correct 41 ms 44600 KB Output is correct
18 Correct 29 ms 44600 KB Output is correct
19 Correct 33 ms 44600 KB Output is correct
20 Correct 30 ms 44600 KB Output is correct
21 Correct 29 ms 44600 KB Output is correct
22 Correct 44 ms 44600 KB Output is correct
23 Correct 31 ms 44600 KB Output is correct
24 Correct 38 ms 44600 KB Output is correct
25 Correct 225 ms 44600 KB Output is correct
26 Correct 393 ms 44600 KB Output is correct
27 Correct 610 ms 44600 KB Output is correct
28 Correct 673 ms 44600 KB Output is correct
29 Correct 901 ms 44600 KB Output is correct
30 Correct 812 ms 44600 KB Output is correct