oj.uz

Submission #673265

# Submission time Handle Problem Language Result Execution time Memory
673265 2022-12-20T04:08:24 Z Cutebol Schools (IZhO13_school) C++17
70 / 100
 2000 ms 28528 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 3e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e12 ;

int n , k , m , sum ;
int	pref[N] , suf[N] ;
int a[N] , b[N] ;
multiset <int> st ;

void solve(){
	
	cin >> n >> m >> k ;
	for ( int i = 0 ; i < n ; i ++ ) cin >> a[i] >> b[i] ;
	vector < pair <int , pair <int , int> > > vec ;
	for ( int i = 0 ; i < n ; i ++ )
		vec.push_back({a[i]-b[i],{a[i],b[i]}}) ;
	sort ( vec.rbegin() , vec.rend() ) ;
	for ( int i = 0 ; i < m ; i ++ ){
		st.insert(vec[i].ss.ff) ;
		sum += vec[i].ss.ff ;
	}
	pref[m-1] = sum ;
	for ( int i = m ; i < n ; i ++ ){
		if ( vec[i].ss.ff > *st.begin() ){
			sum -= *st.begin() ;
			st.erase(st.begin()) ;
			st.insert(vec[i].ss.ff) ;
			sum += vec[i].ss.ff ;
		}
		pref[i] = sum ;
	}
	st.clear() ;
	sum = 0 ;
	for ( int i = n - 1 ; i >= n - k ; i -- ){
		st.insert(vec[i].ss.ss) ;
		sum += vec[i].ss.ss ;
	}
	suf[n-k] = sum ;
	for ( int i = n - k - 1 ; i >= 0 ; i -- ){
		if ( vec[i].ss.ss > *st.begin() ){
			sum -= *st.begin() ;
			st.erase(st.begin()) ;
			st.insert(vec[i].ss.ss) ;
			sum += vec[i].ss.ss ;
		}
		suf[i] = sum ;
	}
	int ans = 0 ;
	for ( int i = m-1 ; i < n ; i ++ ) ans = max ( ans , pref[i]+suf[i+1] ) ;
	cout << ans << endl ;
	for ( int i = 0 ; i < n ; i ++ ) cerr << vec[i].ff << ' ' << vec[i].ss.ff << ' ' << vec[i].ss.ss << endl ;
	for ( int i = 0 ; i < n ; i ++ ) cerr << pref[i] << ' ' << suf[i] << endl ;
}
 
signed main(){
//  fopn("blocks") ;
//    Scaramouche ;
    int t = 1 ;
//    	cin >> t ;
    while ( t -- ) solve() ; 
}

Compilation message

school.cpp: In function 'void fopn(std::string)':
school.cpp:5:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:5:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2093 ms 212 KB Time limit exceeded
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 312 KB Output is correct
7 Correct 53 ms 788 KB Output is correct
8 Correct 55 ms 928 KB Output is correct
9 Correct 55 ms 864 KB Output is correct
10 Correct 56 ms 888 KB Output is correct
11 Correct 59 ms 900 KB Output is correct
12 Correct 59 ms 856 KB Output is correct
13 Correct 450 ms 4896 KB Output is correct
14 Correct 936 ms 8872 KB Output is correct
15 Correct 1882 ms 16704 KB Output is correct
16 Execution timed out 2092 ms 23292 KB Time limit exceeded
17 Execution timed out 2097 ms 23324 KB Time limit exceeded
18 Execution timed out 2052 ms 24148 KB Time limit exceeded
19 Execution timed out 2069 ms 25448 KB Time limit exceeded
20 Execution timed out 2077 ms 28528 KB Time limit exceeded