Submission #1119864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119864	2024-11-27T14:12:22 Z	Hduong	Art Exhibition (JOI18_art)	C++17	30 / 100	5 ms	760 KB

art

#include <bits/stdc++.h>
#define INF 1e18
#define task "task"

using namespace std;
const int N = 5e5 + 5,
          M = 20;
long long a[N], b[N], n, x[M], res = 0, sum[N];
pair <long long, long long> pi[N];

void check() {
  long long sum = 0, mi = INF, ma = -INF, ok = 0;
  for (int i = 1; i <= n; i++) {
    if (x[i] == 0) continue ;
    sum += b[i];
    mi = min(mi, a[i]);
    ma = max(ma, a[i]);
    ++ok;
  }
  if (ok < 1) return ;
  res = max(res, sum - ma + mi);
}

void duyet(long long i) {
  if (i > n) check();
  else {
    for (int j = 0; j < 2; j++) {
      x[i] = j;
      duyet(i + 1);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  if (fopen (task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    pi[i].first = a[i];
    pi[i].second = b[i];
  }
  if (n <= 20) {
    duyet(1);
    cout << res;
  }
  else if (n <= 3000) {
    long long res = 0;
    sort(pi + 1, pi + n + 1);
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + pi[i].second;
    for (int l = 1; l < n; l++) {
      for (int r = l + 1; r <= n; r++) {
        res = max(res, sum[r] - sum[l - 1] - pi[r].first + pi[l].first);
      }
    }
    cout << res << "\n";
  }
}

Compilation message

art.cpp: In function 'int main()':
art.cpp:39:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:40:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	4 ms	336 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	4 ms	480 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	4 ms	336 KB	Output is correct
7	Correct	5 ms	336 KB	Output is correct
8	Correct	4 ms	336 KB	Output is correct
9	Correct	3 ms	336 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	4 ms	484 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	4 ms	336 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	4 ms	480 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	4 ms	336 KB	Output is correct
7	Correct	5 ms	336 KB	Output is correct
8	Correct	4 ms	336 KB	Output is correct
9	Correct	3 ms	336 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	4 ms	484 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	504 KB	Output is correct
20	Correct	1 ms	472 KB	Output is correct
21	Correct	1 ms	336 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	336 KB	Output is correct
24	Correct	1 ms	336 KB	Output is correct
25	Correct	1 ms	336 KB	Output is correct
26	Correct	1 ms	504 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	4 ms	336 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	4 ms	480 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	4 ms	336 KB	Output is correct
7	Correct	5 ms	336 KB	Output is correct
8	Correct	4 ms	336 KB	Output is correct
9	Correct	3 ms	336 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	4 ms	484 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	504 KB	Output is correct
20	Correct	1 ms	472 KB	Output is correct
21	Correct	1 ms	336 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	336 KB	Output is correct
24	Correct	1 ms	336 KB	Output is correct
25	Correct	1 ms	336 KB	Output is correct
26	Correct	1 ms	504 KB	Output is correct
27	Incorrect	2 ms	760 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	4 ms	336 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	4 ms	480 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	4 ms	336 KB	Output is correct
7	Correct	5 ms	336 KB	Output is correct
8	Correct	4 ms	336 KB	Output is correct
9	Correct	3 ms	336 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	4 ms	484 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	504 KB	Output is correct
20	Correct	1 ms	472 KB	Output is correct
21	Correct	1 ms	336 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct
23	Correct	1 ms	336 KB	Output is correct
24	Correct	1 ms	336 KB	Output is correct
25	Correct	1 ms	336 KB	Output is correct
26	Correct	1 ms	504 KB	Output is correct
27	Incorrect	2 ms	760 KB	Output isn't correct
28	Halted	0 ms	0 KB	-