Submission #682689

#TimeUsernameProblemLanguageResultExecution timeMemory
682689Ronin13Schools (IZhO13_school)C++14
95 / 100
299 ms23216 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<ll,ll> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int nmax =5e5 + 1; const ll linf = 1e18 + 1; ll DP[nmax], dp[nmax]; ll A[nmax], B[nmax]; int main(){ // freopen("school.in", "r", stdin); // freopen("school.out", "w", stdout); int n; cin >> n; int m; cin >> m; int s; cin >> s; for(int i = 1; i <= n; i++) cin >> A[i] >> B[i]; vector <pll> vec; for(int i = 1; i <= n; i++){ vec.pb({B[i] - A[i], i}); } sort(vec.begin(), vec.end()); multiset <ll> cur; for(int i = 0; i < vec.size(); i++){ int x = vec[i].s; if(cur.size() < m) DP[i + 1] = DP[i] + A[x], cur.insert(A[x]); else{ DP[i + 1] = DP[i]; if(A[x] < *cur.begin()) continue; DP[i + 1] = DP[i] - *cur.begin() + A[x]; cur.insert(A[x]); cur.erase(cur.begin()); } } cur.clear(); for(int i = vec.size() - 1; i >= 0; i--){ int x = vec[i].s; if(cur.size() < s) dp[i + 1] = dp[i + 2] + B[x], cur.insert(B[x]); else{ dp[i + 1] = dp[i + 2]; if(B[x] < *cur.begin()) continue; dp[i + 1] = dp[i + 2] - *cur.begin() + B[x]; cur.insert(B[x]); cur.erase(cur.begin()); } } ll ans = 0; for(int i = 0; i <= n; i++) ans = max(ans, DP[i] + dp[i + 1]); cout << ans; return 0; }

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
school.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         if(cur.size() < m)
      |            ~~~~~~~~~~~^~~
school.cpp:46:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(cur.size() < s)
      |                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...