Submission #43538

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
43538	2018-03-17T12:29:16 Z	wxh010910	Art Exhibition (JOI18_art)	C++14	50 / 100	41 ms	8756 KB

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

LL ans, val, a[N], b[N];
int n, p[N];

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n);
  for (int i = 1; i <= n; ++i) {
    Read(a[i]), Read(b[i]), p[i] = i;
  }
  sort(p + 1, p + n + 1, [&](const int &x, const int &y) {
    return a[x] < a[y];
  });
  for (int i = 1; i <= n; ++i) {
    b[p[i]] += b[p[i - 1]];
    CheckMax(val, a[p[i]] - b[p[i - 1]]);
    CheckMax(ans, val + b[p[i]] - a[p[i]]);
  }
  printf("%lld\n", ans);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	1 ms	412 KB	Output is correct
4	Correct	1 ms	416 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	728 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	736 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	1 ms	412 KB	Output is correct
4	Correct	1 ms	416 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	728 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	736 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	860 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	2 ms	860 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	2 ms	860 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct
21	Correct	2 ms	896 KB	Output is correct
22	Correct	2 ms	904 KB	Output is correct
23	Correct	2 ms	912 KB	Output is correct
24	Correct	2 ms	924 KB	Output is correct
25	Correct	2 ms	932 KB	Output is correct
26	Correct	2 ms	940 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	1 ms	412 KB	Output is correct
4	Correct	1 ms	416 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	728 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	736 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	860 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	2 ms	860 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	2 ms	860 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct
21	Correct	2 ms	896 KB	Output is correct
22	Correct	2 ms	904 KB	Output is correct
23	Correct	2 ms	912 KB	Output is correct
24	Correct	2 ms	924 KB	Output is correct
25	Correct	2 ms	932 KB	Output is correct
26	Correct	2 ms	940 KB	Output is correct
27	Correct	3 ms	1076 KB	Output is correct
28	Correct	3 ms	1204 KB	Output is correct
29	Correct	3 ms	1332 KB	Output is correct
30	Correct	3 ms	1460 KB	Output is correct
31	Correct	3 ms	1588 KB	Output is correct
32	Correct	5 ms	1716 KB	Output is correct
33	Correct	3 ms	1868 KB	Output is correct
34	Correct	3 ms	1972 KB	Output is correct
35	Correct	3 ms	2100 KB	Output is correct
36	Correct	4 ms	2228 KB	Output is correct
37	Correct	4 ms	2484 KB	Output is correct
38	Correct	3 ms	2484 KB	Output is correct
39	Correct	3 ms	2644 KB	Output is correct
40	Correct	3 ms	2740 KB	Output is correct
41	Correct	3 ms	2868 KB	Output is correct
42	Correct	3 ms	3016 KB	Output is correct
43	Correct	3 ms	3120 KB	Output is correct
44	Correct	4 ms	3276 KB	Output is correct
45	Correct	4 ms	3376 KB	Output is correct
46	Correct	3 ms	3524 KB	Output is correct
47	Correct	3 ms	3632 KB	Output is correct
48	Correct	5 ms	3764 KB	Output is correct
49	Correct	3 ms	3888 KB	Output is correct
50	Correct	4 ms	4016 KB	Output is correct
51	Correct	3 ms	4168 KB	Output is correct

Subtask #4
0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	1 ms	412 KB	Output is correct
4	Correct	1 ms	416 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	728 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	736 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	860 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	2 ms	860 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	2 ms	860 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	872 KB	Output is correct
21	Correct	2 ms	896 KB	Output is correct
22	Correct	2 ms	904 KB	Output is correct
23	Correct	2 ms	912 KB	Output is correct
24	Correct	2 ms	924 KB	Output is correct
25	Correct	2 ms	932 KB	Output is correct
26	Correct	2 ms	940 KB	Output is correct
27	Correct	3 ms	1076 KB	Output is correct
28	Correct	3 ms	1204 KB	Output is correct
29	Correct	3 ms	1332 KB	Output is correct
30	Correct	3 ms	1460 KB	Output is correct
31	Correct	3 ms	1588 KB	Output is correct
32	Correct	5 ms	1716 KB	Output is correct
33	Correct	3 ms	1868 KB	Output is correct
34	Correct	3 ms	1972 KB	Output is correct
35	Correct	3 ms	2100 KB	Output is correct
36	Correct	4 ms	2228 KB	Output is correct
37	Correct	4 ms	2484 KB	Output is correct
38	Correct	3 ms	2484 KB	Output is correct
39	Correct	3 ms	2644 KB	Output is correct
40	Correct	3 ms	2740 KB	Output is correct
41	Correct	3 ms	2868 KB	Output is correct
42	Correct	3 ms	3016 KB	Output is correct
43	Correct	3 ms	3120 KB	Output is correct
44	Correct	4 ms	3276 KB	Output is correct
45	Correct	4 ms	3376 KB	Output is correct
46	Correct	3 ms	3524 KB	Output is correct
47	Correct	3 ms	3632 KB	Output is correct
48	Correct	5 ms	3764 KB	Output is correct
49	Correct	3 ms	3888 KB	Output is correct
50	Correct	4 ms	4016 KB	Output is correct
51	Correct	3 ms	4168 KB	Output is correct
52	Incorrect	41 ms	8756 KB	Output isn't correct
53	Halted	0 ms	0 KB	-

Submission #43538

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 50.0