oj.uz

Submission #145722

# Submission time Handle Problem Language Result Execution time Memory
145722 2019-08-20T22:26:25 Z osaaateiasavtnl Candies (JOI18_candies) C++14
0 / 100
 24 ms 376 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int a[N];
bool used[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    for (int _ = 1; _ <= (n + 1) / 2; ++_) {
        int mx = -INF;
        for (int i = 1; i <= n; ++i) {
            if (!used[i] && !used[i - 1] && !used[i + 1]) mx = max(mx, a[i]);
        }
        vector <int> p;
        for (int i = 1; i <= n; ++i) {
            if (used[i]) p.app(i);
        }
        int l = 0;
        while (l < p.size()) {
            int r = l;
            while (r + 1 < p.size() && p[r + 1] == p[l] + 2) ++r;
            if (1 < p[l] && p[r] < n) {
                int sum = a[p[l] - 1] + a[p[r] + 1];
                for (int i = p[l] + 1; i < p[r]; i += 2) sum += a[i];
                for (int i = p[l]; i <= p[r]; i += 2) sum -= a[i];
                mx = max(mx, sum);
            }
            l = r + 1;
        }

        ans += mx;

        bool mem = 0;
        for (int i = 1; i <= n; ++i) {
            if (!used[i] && !used[i - 1] && !used[i + 1] && a[i] == mx) {
                used[i] = 1; mem = 1; break;
            }
        }
        if (!mem) {
            l = 0;
            while (l < p.size()) {
                int r = l;
                while (r + 1 < p.size() && p[r + 1] == p[l] + 2) ++r;
                if (1 < p[l] && p[r] < n) {
                    int sum = a[p[l] - 1] + a[p[r] + 1];
                    for (int i = p[l] + 1; i < p[r]; i += 2) sum += a[i];
                    for (int i = p[l]; i <= p[r]; i += 2) sum -= a[i];
                    if (sum == mx) {
                        used[p[l] - 1] = used[p[r] + 1] = 1;
                        for (int i = p[l] + 1; i < p[r]; i += 2) used[i] = 1;
                        for (int i = p[l]; i <= p[r]; i += 2) used[i] = 0;
                        break;
                    }
                }
                l = r + 1;
            }       
        }

        cout << ans << '\n';
    }
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (l < p.size()) {
                ~~^~~~~~~~~~
candies.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (r + 1 < p.size() && p[r + 1] == p[l] + 2) ++r;
                    ~~~~~~^~~~~~~~~~
candies.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (l < p.size()) {
                    ~~^~~~~~~~~~
candies.cpp:53:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while (r + 1 < p.size() && p[r + 1] == p[l] + 2) ++r;
                        ~~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -