Submission #467280

#TimeUsernameProblemLanguageResultExecution timeMemory
467280ivan_tudorHoliday (IOI14_holiday)C++14
0 / 100
71 ms6616 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; const int N = 100005; int a[N]; multiset<int> big, small; long long sum; int canhold; int L, R; void insert_val(int v){ big.insert(v); sum += v; while(big.size() && big.size() > canhold){ int lval = (*big.begin()); sum -= lval; big.erase(big.begin()); small.insert(lval); } } void erase_val(int v){ if(small.count(v)){ small.erase(small.find(v)); } else if(big.count(v)){ big.erase(big.find(v)); sum -= v; } while(big.size() < canhold && small.size()){ int val = (*small.rbegin()); big.insert(val); sum += val; small.erase(small.find(val)); } } void transf(int newL, int newR){ while(L > newL){ canhold -=2; L--; insert_val(a[L]); } while(R < newR){ canhold --; R++; insert_val(a[R]); } while(L < newL){ canhold +=2; erase_val(a[L]); L++; } while(R > newR){ canhold++; erase_val(a[R]); R--; } } long long ans = 0; void solve(int l, int r, int opl, int opr){ int mid = (l + r)/2; long long maxi = -1, mpoz; for(int i = max(opl, mid); i <= opr; i++){ transf(mid, i); if(maxi < sum){ maxi = sum; mpoz = i; } } ans = max(ans, maxi); if(l == r) return; solve(l, mid, opl, mpoz); solve(mid + 1, r, mpoz + 1, opr); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { for(int i = 0; i < n; i++) a[i] = attraction[i]; insert_val(a[start]); L = R = start; canhold = d; solve(0, start, start, n - 1); reverse(a, a+n); start = n - 1 - start; big.clear(); small.clear(); sum = 0; insert_val(a[start]); L = R = start; canhold = d; solve(0, start, start, n - 1); return ans; }

Compilation message (stderr)

holiday.cpp: In function 'void insert_val(int)':
holiday.cpp:13:34: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |   while(big.size() && big.size() > canhold){
      |                       ~~~~~~~~~~~^~~~~~~~~
holiday.cpp: In function 'void erase_val(int)':
holiday.cpp:29:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   while(big.size() < canhold && small.size()){
      |         ~~~~~~~~~~~^~~~~~~~~
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:74:26: warning: 'mpoz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |   solve(mid + 1, r, mpoz + 1, opr);
      |                     ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...