oj.uz

답안 #90814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90814 2018-12-24T14:18:49 Z YottaByte 학교 설립 (IZhO13_school) C++14
25 / 100
 416 ms 27088 KB 
#include <bits/stdc++.h>

#define pb push_back
#define mk make_pair
#define fr first
#define sc second

using namespace std;

const int N = 3e5 + 5;

int n, x, y, must[N * 4];

pair <int, int> t[N * 4];

pair <int, int> a[N];

long long ans;

void push(int v, int tl, int tr)
{
	t[v].fr += must[v];
	
	if (tl != tr)
	{
		must[v + v] += must[v];
		must[v + v + 1] += must[v];
	}
	
	must[v] = 0;
}

void upd (int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
	push(v, tl, tr);
	
	if (tl > r || l > tr) return;
	
	if (l <= tl && tr <= r)
	{
		must[v] += val;
		push(v, tl, tr);
		return ;
	}
	int tm = (tl + tr) >> 1;
	upd(l, r, val, v + v, tl, tm);
	upd(l, r, val, v + v + 1, tm + 1, tr);
		
	t[v] = max( t[v + v], t[v + v + 1] );
}
void build (int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		if (tl <= x)
			t[v] = mk( -a[tl].fr + a[tl].sc + a[x + 1].fr, tl );
		else
			t[v] = mk( a[tl].sc, tl );
	}
	else
	{
		int tm = (tl + tr) >> 1;
		build( v + v, tl, tm );
		build( v + v + 1, tm + 1, tr );
		t[v] = max(t[v + v], t[v + v + 1]);
	}
}
set <int> st;

main()
{
	cin >> n >> x >> y;
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i].fr, &a[i].sc);
	}
	sort( a + 1, a + n + 1, greater < pair <int, int> >() );
	
	for (int i = 1; i <= x; i++)
		ans += a[i].fr;
	for (int i = x + 1; i <= n; i++)
		st.insert(i);
		
	build();
	
	while(y--)
	{
		if ( st.count( t[1].sc ) )
		{
			int val = t[1].fr, ind = t[1].sc;
			
			ans += t[1].fr;
			
			upd( 1, x, -a[*st.begin()].fr );
			upd( ind, ind, -1e9 - 7 );
			
			st.erase(ind );
			
			if (!st.empty())
				upd( 1, x, +a[*st.begin()].fr );
		}
		else
		{
			int val = t[1].fr, ind = t[1].sc;
			
			ans += t[1].fr;
			
			upd( 1, x, -a[*st.begin()].fr );
			
			upd( *st.begin(), *st.begin(), -1e9 - 7 );
			st.erase(st.begin());
			
			if (!st.empty())
				upd( 1, x, +a[*st.begin()].fr );
				
			upd( ind, ind, -1e9 - 7 );
		}
	}
	cout << ans << endl;
}
/**
5 3 2
41 36
47 16
27 2
29 4
33 30


**/

Compilation message

school.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
school.cpp: In function 'int main()':
school.cpp:91:8: warning: unused variable 'val' [-Wunused-variable]
    int val = t[1].fr, ind = t[1].sc;
        ^~~
school.cpp:105:8: warning: unused variable 'val' [-Wunused-variable]
    int val = t[1].fr, ind = t[1].sc;
        ^~~
school.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].fr, &a[i].sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Correct 2 ms 512 KB Output is correct
6 Incorrect 2 ms 728 KB Output isn't correct
7 Incorrect 5 ms 924 KB Output isn't correct
8 Incorrect 3 ms 924 KB Output isn't correct
9 Incorrect 4 ms 924 KB Output isn't correct
10 Incorrect 3 ms 976 KB Output isn't correct
11 Incorrect 7 ms 1280 KB Output isn't correct
12 Incorrect 7 ms 1348 KB Output isn't correct
13 Incorrect 15 ms 2980 KB Output isn't correct
14 Incorrect 79 ms 8756 KB Output isn't correct
15 Correct 114 ms 17340 KB Output is correct
16 Incorrect 416 ms 17820 KB Output isn't correct
17 Incorrect 265 ms 17820 KB Output isn't correct
18 Incorrect 225 ms 17844 KB Output isn't correct
19 Incorrect 276 ms 18868 KB Output isn't correct
20 Incorrect 347 ms 27088 KB Output isn't correct