oj.uz

답안 #70389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70389 2018-08-22T18:58:28 Z elitewantsyou Candies (JOI18_candies) C++14
0 / 100
 5 ms 504 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 200200;
const long long Q = 200200;
const long long mod = 998244353;
const long long MAGIC = sqrt(N);

using namespace std;

int n;
long long a[N];
set < int > s;
set < pair < long long, int > > f;

void solve()
{
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
        }
        a[1] = a[n + 1] = -1e15;
        for(int i = 0; i <= n + 1; i++){
                s.insert(i);
                f.insert({a[i], i});
        }
        long long ans = 0;
        for(int i = 1; i <= (n + 1) / 2; i++){
                int x = (--f.end())->se;
                f.erase(--f.end());
                s.erase(x);
                ans += a[x];
                long long ad = -a[x];
                auto p = s.lower_bound(x);
                if(p != s.end()){
                        ad += a[*p];
                        f.erase({a[*p], *p});
                        s.erase(p);
                }
                p = s.lower_bound(x);
                if(p != s.begin()){
                        p--;
                        ad += a[*p];
                        f.erase({a[*p], *p});
                        s.erase(p);
                }
                a[x] = ad;
                s.insert(x);
                f.insert({ad, x});
                cout << ans << "\n";
        }
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("island.in");
        //fout("island.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -