Submission #1042816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042816		votranngocvy	Holiday (IOI14_holiday)	C++14	47 / 100	202 ms	2856 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

#define NAME "task"
#define int long long

const int N = 1e5 + 5;
int n,s,d,a[N],ans = 0;

namespace sub2 {
    void solve() {
        priority_queue<int,vector<int>,greater<int>>q;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            q.push(a[i]);
            cur += a[i];
            while (!q.empty() && i + q.size() > d) {
                cur -= q.top();
                q.pop();
            }
            ans = max(ans,cur);
        }
        //cout << ans << "\n";
    }
}

namespace sub3 {
    void solve() {
        for (int i = s; i >= 0; i--) {
            if (s - i > d) break;
            priority_queue<int,vector<int>,greater<int>>q;
            int j = s,cur = 0;
            while (j >= i) {
                q.push(a[j]);
                cur += a[j];
                while (!q.empty() && s - j + q.size() > d) {
                    cur -= q.top();
                    q.pop();
                }
                ans = max(ans,cur);
                j--;
            }
            j = s + 1;
            while (j < n) {
                q.push(a[j]);
                cur += a[j];
                while (!q.empty() && s - i + j - i + q.size() > d) {
                    cur -= q.top();
                    q.pop();
                }
                ans = max(ans,cur);
                j++;
            }
        }
        reverse(a,a + n);
        s = n - s - 1;
        for (int i = s; i >= 0; i--) {
            if (s - i > d) break;
            priority_queue<int,vector<int>,greater<int>>q;
            int j = s,cur = 0;
            while (j >= i) {
                q.push(a[j]);
                cur += a[j];
                while (!q.empty() && s - j + q.size() > d) {
                    cur -= q.top();
                    q.pop();
                }
                ans = max(ans,cur);
                j--;
            }
            j = s + 1;
            while (j < n) {
                q.push(a[j]);
                cur += a[j];
                while (!q.empty() && s - i + j - i + q.size() > d) {
                    cur -= q.top();
                    q.pop();
                }
                ans = max(ans,cur);
                j++;
            }
        }
        //cout << ans << "\n";
    }
}

int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t attraction[]) {
    s = S;
    d = D;
    n = N;
    for (int i = 0; i < n; i++) a[i] = attraction[i];
    if (s == 0) sub2::solve();
    else if (n <= 3e3) sub3::solve();
    return ans;
}

/*signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen(NAME".inp","r",stdin);
    freopen(NAME".out","w",stdout);
    cin >> n >> s >> d;  
    for (int i = 0; i < n; i++) cin >> a[i]; 
    if (s == 0) sub2::solve();
    else if (n <= 3e3) sub3::solve();
}*/

Compilation message (stderr)

holiday.cpp: In function 'void sub2::solve()':
holiday.cpp:17:47: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   17 |             while (!q.empty() && i + q.size() > d) {
      |                                  ~~~~~~~~~~~~~^~~
holiday.cpp: In function 'void sub3::solve()':
holiday.cpp:36:55: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   36 |                 while (!q.empty() && s - j + q.size() > d) {
      |                                      ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:47:63: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   47 |                 while (!q.empty() && s - i + j - i + q.size() > d) {
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:64:55: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   64 |                 while (!q.empty() && s - j + q.size() > d) {
      |                                      ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:75:63: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   75 |                 while (!q.empty() && s - i + j - i + q.size() > d) {
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53