Submission #674448

#	Time	Username	Problem	Language	Result	Execution time	Memory
674448		ddy888	Hacker (BOI15_hac)	C++17	100 / 100	306 ms	26268 KiB

hac

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 500010;
int n;
int arr[MAXN*3],ps[MAXN*3],ans;
multiset<int> ms;

int sum(int l, int r) {return ps[r]-ps[l-1];}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        arr[i+n]=arr[i];
        arr[i+2*n]=arr[i];
    } 
    for (int i = 1; i <= 3*n; ++i) {
        ps[i] = ps[i-1]+arr[i];
    }
    int k = (n+1)/2;
    for (int i = n+1,j=n+1-k; i <= 2*n; ++i) {
        while (ms.size()<k) {
            ++j;
            ms.insert(sum(j,j+k-1));
        }
        chmax(ans, *ms.begin());
        ms.erase(ms.find(sum(i-k+1,i)));
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:39:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |         while (ms.size()<k) {
      |                ~~~~~~~~~^~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40