oj.uz

답안 #224189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224189 2020-04-17T12:02:07 Z _7_7_ Cake 3 (JOI19_cake3) C++14
100 / 100
 1311 ms 207972 KB 
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 
 
int n, k, ans = -INF, b[N];
pii a[N];
vi x;

struct node {
	node *l, *r;
	int cnt, sum;

	node () {
		l = r = NULL;
		sum = cnt = 0;
	}

	node (int c, int s, int x) {
		l = r = NULL;
		cnt = c;
		sum = s;
	}

	node (node *L, node *R) {
		l = L;
		r = R;
		cnt = (!l ? 0 : l->cnt) + (!r ? 0 : r->cnt);
		sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
	}
};
typedef node * pnode;
pnode root[N];

pnode build (int tl = 0, int tr = N) {
	if (tl == tr) 
		return new node();
	int tm = (tl + tr) >> 1;
	return new node(build(tl, tm), build(tm + 1, tr));
}

pnode update (pnode t, int pos, int tl = 0, int tr = N) {
	if (tl == tr)
		return new node(t->cnt + 1, t->sum + x[sz(x) - 1 - pos], 0);
	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		return new node(update(t->l, pos, tl, tm), t->r);
	return new node(t->l, update(t->r, pos, tm + 1, tr));
}


int get (pnode t1, pnode t2, int k, int tl = 0, int tr = N) {
	if (!k)
		return 0;
	if (tl == tr) 
		return x[sz(x) - tl - 1] * k; 
	
	int tm = (tl + tr) >> 1;
	if (t1->l->cnt - t2->l->cnt >= k)
		return get(t1->l, t2->l, k, tl, tm);
	return t1->l->sum - t2->l->sum + get(t1->r, t2->r, k - t1->l->cnt + t2->l->cnt, tm + 1, tr);
}

int cost (int l, int r) {
	return a[l].f + a[l].s + a[r].s - a[r].f + get(root[r - 1], root[l], k - 2);
}

void calc (int l = 1, int r = n - k + 1, int tl = 1, int tr = n) {
	if (l > r)
		return;
	int m = (l + r) >> 1, mx = -INF, tm = -1;
	for (int i = max(m + k - 1, tl); i <= tr; ++i) {
		int cur = cost(m, i);
		if (cur > mx) {
			mx = cur;
			tm = i;
		}
	}

	ans = max(ans, mx);
	calc(l, m - 1, tl, tm);
	calc(m + 1, r, tm, tr);
}



main () {
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &a[i].s, &a[i].f); 
		a[i].f += a[i].f;
		x.pb(a[i].s);
	}
	
	sort(a + 1, a + 1 + n);
		
	sort(all(x));
	x.resize(unique(all(x)) - x.begin());

	root[0] = build();	
	for (int i = 1; i <= n; ++i) {
		b[i] = lower_bound(all(x), a[i].s) - x.begin();
		root[i] = update(root[i - 1], sz(x) - 1 - b[i]);
	}

	calc();
	cout << ans << endl;	
}

Compilation message

cake3.cpp:122:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
cake3.cpp: In function 'int main()':
cake3.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &a[i].s, &a[i].f); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 19200 KB Output is correct
2 Correct 24 ms 19200 KB Output is correct
3 Correct 26 ms 19200 KB Output is correct
4 Correct 26 ms 19328 KB Output is correct
5 Correct 24 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 24 ms 19320 KB Output is correct
8 Correct 26 ms 19200 KB Output is correct
9 Correct 24 ms 19200 KB Output is correct
10 Correct 26 ms 19196 KB Output is correct
11 Correct 24 ms 19200 KB Output is correct
12 Correct 24 ms 19200 KB Output is correct
13 Correct 23 ms 19192 KB Output is correct
14 Correct 24 ms 19200 KB Output is correct
15 Correct 23 ms 19200 KB Output is correct
16 Correct 27 ms 19200 KB Output is correct
17 Correct 26 ms 19200 KB Output is correct
18 Correct 23 ms 19200 KB Output is correct
19 Correct 23 ms 19200 KB Output is correct
20 Correct 26 ms 19192 KB Output is correct
21 Correct 26 ms 19200 KB Output is correct
22 Correct 25 ms 19200 KB Output is correct
23 Correct 25 ms 19200 KB Output is correct
24 Correct 23 ms 19200 KB Output is correct
25 Correct 23 ms 19200 KB Output is correct
26 Correct 27 ms 19192 KB Output is correct
27 Correct 23 ms 19200 KB Output is correct
28 Correct 24 ms 19168 KB Output is correct
29 Correct 24 ms 19200 KB Output is correct
30 Correct 28 ms 19192 KB Output is correct
31 Correct 23 ms 19196 KB Output is correct
32 Correct 24 ms 19200 KB Output is correct
33 Correct 23 ms 19192 KB Output is correct
34 Correct 26 ms 19200 KB Output is correct
35 Correct 24 ms 19192 KB Output is correct
36 Correct 24 ms 19200 KB Output is correct
37 Correct 26 ms 19200 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 19200 KB Output is correct
2 Correct 24 ms 19200 KB Output is correct
3 Correct 26 ms 19200 KB Output is correct
4 Correct 26 ms 19328 KB Output is correct
5 Correct 24 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 24 ms 19320 KB Output is correct
8 Correct 26 ms 19200 KB Output is correct
9 Correct 24 ms 19200 KB Output is correct
10 Correct 26 ms 19196 KB Output is correct
11 Correct 24 ms 19200 KB Output is correct
12 Correct 24 ms 19200 KB Output is correct
13 Correct 23 ms 19192 KB Output is correct
14 Correct 24 ms 19200 KB Output is correct
15 Correct 23 ms 19200 KB Output is correct
16 Correct 27 ms 19200 KB Output is correct
17 Correct 26 ms 19200 KB Output is correct
18 Correct 23 ms 19200 KB Output is correct
19 Correct 23 ms 19200 KB Output is correct
20 Correct 26 ms 19192 KB Output is correct
21 Correct 26 ms 19200 KB Output is correct
22 Correct 25 ms 19200 KB Output is correct
23 Correct 25 ms 19200 KB Output is correct
24 Correct 23 ms 19200 KB Output is correct
25 Correct 23 ms 19200 KB Output is correct
26 Correct 27 ms 19192 KB Output is correct
27 Correct 23 ms 19200 KB Output is correct
28 Correct 24 ms 19168 KB Output is correct
29 Correct 24 ms 19200 KB Output is correct
30 Correct 28 ms 19192 KB Output is correct
31 Correct 23 ms 19196 KB Output is correct
32 Correct 24 ms 19200 KB Output is correct
33 Correct 23 ms 19192 KB Output is correct
34 Correct 26 ms 19200 KB Output is correct
35 Correct 24 ms 19192 KB Output is correct
36 Correct 24 ms 19200 KB Output is correct
37 Correct 26 ms 19200 KB Output is correct
38 Correct 28 ms 20856 KB Output is correct
39 Correct 30 ms 20992 KB Output is correct
40 Correct 28 ms 20864 KB Output is correct
41 Correct 29 ms 20864 KB Output is correct
42 Correct 27 ms 20992 KB Output is correct
43 Correct 27 ms 20856 KB Output is correct
44 Correct 28 ms 20864 KB Output is correct
45 Correct 27 ms 20992 KB Output is correct
46 Correct 28 ms 20992 KB Output is correct
47 Correct 28 ms 20864 KB Output is correct
48 Correct 28 ms 20856 KB Output is correct
49 Correct 28 ms 20992 KB Output is correct
50 Correct 28 ms 20992 KB Output is correct
51 Correct 28 ms 20992 KB Output is correct
52 Correct 27 ms 20864 KB Output is correct
53 Correct 27 ms 20984 KB Output is correct
54 Correct 27 ms 20984 KB Output is correct
55 Correct 29 ms 20864 KB Output is correct
56 Correct 30 ms 20856 KB Output is correct
57 Correct 26 ms 20864 KB Output is correct
58 Correct 26 ms 20864 KB Output is correct
59 Correct 28 ms 20856 KB Output is correct
60 Correct 29 ms 20864 KB Output is correct
61 Correct 29 ms 20992 KB Output is correct
62 Correct 27 ms 20992 KB Output is correct
63 Correct 27 ms 20984 KB Output is correct
64 Correct 25 ms 20992 KB Output is correct
65 Correct 28 ms 20936 KB Output is correct
66 Correct 30 ms 20860 KB Output is correct
67 Correct 28 ms 20864 KB Output is correct
68 Correct 27 ms 20984 KB Output is correct
69 Correct 28 ms 20856 KB Output is correct
70 Correct 28 ms 20992 KB Output is correct
71 Correct 28 ms 20864 KB Output is correct
72 Correct 27 ms 20892 KB Output is correct
73 Correct 29 ms 20892 KB Output is correct
74 Correct 26 ms 20992 KB Output is correct

Subtask #3
76.0 / 76.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 19200 KB Output is correct
2 Correct 24 ms 19200 KB Output is correct
3 Correct 26 ms 19200 KB Output is correct
4 Correct 26 ms 19328 KB Output is correct
5 Correct 24 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 24 ms 19320 KB Output is correct
8 Correct 26 ms 19200 KB Output is correct
9 Correct 24 ms 19200 KB Output is correct
10 Correct 26 ms 19196 KB Output is correct
11 Correct 24 ms 19200 KB Output is correct
12 Correct 24 ms 19200 KB Output is correct
13 Correct 23 ms 19192 KB Output is correct
14 Correct 24 ms 19200 KB Output is correct
15 Correct 23 ms 19200 KB Output is correct
16 Correct 27 ms 19200 KB Output is correct
17 Correct 26 ms 19200 KB Output is correct
18 Correct 23 ms 19200 KB Output is correct
19 Correct 23 ms 19200 KB Output is correct
20 Correct 26 ms 19192 KB Output is correct
21 Correct 26 ms 19200 KB Output is correct
22 Correct 25 ms 19200 KB Output is correct
23 Correct 25 ms 19200 KB Output is correct
24 Correct 23 ms 19200 KB Output is correct
25 Correct 23 ms 19200 KB Output is correct
26 Correct 27 ms 19192 KB Output is correct
27 Correct 23 ms 19200 KB Output is correct
28 Correct 24 ms 19168 KB Output is correct
29 Correct 24 ms 19200 KB Output is correct
30 Correct 28 ms 19192 KB Output is correct
31 Correct 23 ms 19196 KB Output is correct
32 Correct 24 ms 19200 KB Output is correct
33 Correct 23 ms 19192 KB Output is correct
34 Correct 26 ms 19200 KB Output is correct
35 Correct 24 ms 19192 KB Output is correct
36 Correct 24 ms 19200 KB Output is correct
37 Correct 26 ms 19200 KB Output is correct
38 Correct 28 ms 20856 KB Output is correct
39 Correct 30 ms 20992 KB Output is correct
40 Correct 28 ms 20864 KB Output is correct
41 Correct 29 ms 20864 KB Output is correct
42 Correct 27 ms 20992 KB Output is correct
43 Correct 27 ms 20856 KB Output is correct
44 Correct 28 ms 20864 KB Output is correct
45 Correct 27 ms 20992 KB Output is correct
46 Correct 28 ms 20992 KB Output is correct
47 Correct 28 ms 20864 KB Output is correct
48 Correct 28 ms 20856 KB Output is correct
49 Correct 28 ms 20992 KB Output is correct
50 Correct 28 ms 20992 KB Output is correct
51 Correct 28 ms 20992 KB Output is correct
52 Correct 27 ms 20864 KB Output is correct
53 Correct 27 ms 20984 KB Output is correct
54 Correct 27 ms 20984 KB Output is correct
55 Correct 29 ms 20864 KB Output is correct
56 Correct 30 ms 20856 KB Output is correct
57 Correct 26 ms 20864 KB Output is correct
58 Correct 26 ms 20864 KB Output is correct
59 Correct 28 ms 20856 KB Output is correct
60 Correct 29 ms 20864 KB Output is correct
61 Correct 29 ms 20992 KB Output is correct
62 Correct 27 ms 20992 KB Output is correct
63 Correct 27 ms 20984 KB Output is correct
64 Correct 25 ms 20992 KB Output is correct
65 Correct 28 ms 20936 KB Output is correct
66 Correct 30 ms 20860 KB Output is correct
67 Correct 28 ms 20864 KB Output is correct
68 Correct 27 ms 20984 KB Output is correct
69 Correct 28 ms 20856 KB Output is correct
70 Correct 28 ms 20992 KB Output is correct
71 Correct 28 ms 20864 KB Output is correct
72 Correct 27 ms 20892 KB Output is correct
73 Correct 29 ms 20892 KB Output is correct
74 Correct 26 ms 20992 KB Output is correct
75 Correct 1208 ms 193724 KB Output is correct
76 Correct 1311 ms 189068 KB Output is correct
77 Correct 863 ms 194024 KB Output is correct
78 Correct 935 ms 196708 KB Output is correct
79 Correct 618 ms 197220 KB Output is correct
80 Correct 556 ms 192184 KB Output is correct
81 Correct 612 ms 194916 KB Output is correct
82 Correct 809 ms 197204 KB Output is correct
83 Correct 714 ms 202984 KB Output is correct
84 Correct 715 ms 202428 KB Output is correct
85 Correct 627 ms 196196 KB Output is correct
86 Correct 500 ms 190312 KB Output is correct
87 Correct 481 ms 188132 KB Output is correct
88 Correct 567 ms 186852 KB Output is correct
89 Correct 595 ms 196452 KB Output is correct
90 Correct 472 ms 204392 KB Output is correct
91 Correct 436 ms 190564 KB Output is correct
92 Correct 405 ms 189156 KB Output is correct
93 Correct 504 ms 196608 KB Output is correct
94 Correct 421 ms 204260 KB Output is correct
95 Correct 495 ms 204772 KB Output is correct
96 Correct 430 ms 194020 KB Output is correct
97 Correct 447 ms 207972 KB Output is correct
98 Correct 502 ms 205156 KB Output is correct
99 Correct 476 ms 205596 KB Output is correct
100 Correct 390 ms 195044 KB Output is correct
101 Correct 476 ms 194916 KB Output is correct
102 Correct 854 ms 192484 KB Output is correct
103 Correct 957 ms 190008 KB Output is correct
104 Correct 994 ms 199416 KB Output is correct
105 Correct 862 ms 198828 KB Output is correct
106 Correct 784 ms 203392 KB Output is correct
107 Correct 604 ms 196860 KB Output is correct
108 Correct 913 ms 195812 KB Output is correct
109 Correct 808 ms 206308 KB Output is correct
110 Correct 387 ms 193764 KB Output is correct
111 Correct 480 ms 195684 KB Output is correct
112 Correct 753 ms 186980 KB Output is correct
113 Correct 581 ms 206444 KB Output is correct