oj.uz

Submission #103346

# Submission time Handle Problem Language Result Execution time Memory
103346 2019-03-29T20:19:17 Z tincamatei Art Exhibition (JOI18_art) C++14
10 / 100
 6 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000;

struct Paint {
	long long a, b;
}v[1+MAX_N];

bool cmp(Paint a, Paint b) {
	return a.a < b.a;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n;
	long long best, rez, sp;

	fscanf(fin, "%d", &n);

	for(int i = 0; i < n; ++i)
		fscanf(fin, "%lld%lld", &v[i].a, &v[i].b);
	sort(v, v + n, cmp);
	
	sp = rez = 0LL;
	best = v[0].a;
	
	for(int i = 1; i < (1 << n); ++i) {
		long long minA, maxA, sum;
		minA = 1LL<<60;
		maxA = -1;
		sum = 0LL;

		for(int j = 0; j < n; ++j)
			if((1 << j) & i) {
				sum += v[j].b;
				minA = min(minA, v[j].a);
				maxA = max(maxA, v[j].a);
			}
		
		rez = max(rez, sum - (maxA - minA));
	}

	/*for(int i = 0; i < n; ++i) {
		sp = 0LL;
		for(int j = i; j < n; ++j) {
			sp += v[j].b;
			rez = max(rez, sp - v[j].a + v[i].a);
			//if(sp - v[j].a + v[i].a == rez)
				//printf("%d %d->%lld\n", i, j, sp - v[j].a + v[i].a);
		}
	}*/

	/*for(int i = 0; i < n; ++i) {
		printf("%lld %lld\n", v[i].a, v[i].b);
		sp = sp + v[i].b;
		rez = max(rez, sp - v[i].a + best);

		best = max(best, -sp + v[i].b + v[i].a);
		printf("!%lld\n", sp);
	} */

	fprintf(fout, "%lld", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message

art.cpp: In function 'int main()':
art.cpp:25:12: warning: variable 'best' set but not used [-Wunused-but-set-variable]
  long long best, rez, sp;
            ^~~~
art.cpp:25:23: warning: variable 'sp' set but not used [-Wunused-but-set-variable]
  long long best, rez, sp;
                       ^~
art.cpp:27:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
art.cpp:30:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%lld%lld", &v[i].a, &v[i].b);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Incorrect 4 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Incorrect 4 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Incorrect 4 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -