제출 #1300119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300119		cehobi	Hacker (BOI15_hac)	C++17	100 / 100	40 ms	20172 KiB

hac

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define ll long long
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define int long long
using namespace std;

template <typename t1, typename t2> bool maximize(t1 &a, const t2 &b){if(a < b){a = b; return 1;} else return 0;};
template <typename t1, typename t2> bool minimize(t1 &a, const t2 &b){if(a > b){a = b; return 1;} else return 0;};

void load(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
}

const int oo = 1e9 + 7;
const ll OO = 1e18 + 7;
const int maxn = 5e5 + 5;
int n;
int a[2 * maxn];
int pref[2 * maxn];
struct pp{
    int val, id;
};
deque<pp> dq;
int k;
int res = 0;

void enter(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i + n] = a[i];
    }
    pref[0] = 0;
    for(int i = 1; i <= n * 2; i++){
        pref[i] = pref[i - 1] + a[i];
    }
}

int get_range(int l, int r){
    return pref[r] - pref[l - 1];
}

void add(int val, int id){
    while(!dq.empty() && dq.back().val > val) dq.pop_back();
    dq.push_back({val, id});
}

void Try(){
    k = (n + 1) / 2;

    for(int i = 1; i <= k; i++){
        add(get_range(i, i + k - 1), i);
    }

    for(int i = k; i <= n + k - 1; i++){
        while(dq.front().id <= i - k) dq.pop_front();

        maximize(res, dq.front().val);
//        for(pp it : dq) cout << "{" << it.val << ", " << it.id << "} "; cout << '\n';
        add(get_range(i + 1, i + k), i + 1);
//        cout << i << ' ' << res << ' ' << '\n';
    }
    cout << res;
}

signed main(){
    load();
    enter();
    Try();

    cerr << '\n' << "Time ran: " << TIME << "s\n";
}

컴파일 시 표준 에러 (stderr) 메시지

hac.cpp: In function 'void load()':
hac.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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