Submission #1042451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042451		lyis	Holiday (IOI14_holiday)	C++14	0 / 100	18 ms	5040 KiB

holiday

#include <holiday.h>
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.shpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
#define fi  first
#define se  second
#define mp  make_pair
 
#define ii  pair <int, int>
#define li  pair <long long, int>
 
using namespace std;
//using namespace __gnu_pbds;
 
//mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
 
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef __int128 i128;
 
const ll        mod = 1e9 + 7;
const ll        MOD = 998245353;
const db        esp = 1e-10;
 
const int dx[] = {0,  1,  0, -1, -1,  1,  1, -1};
const int dy[] = {1,  0, -1,  0, -1, -1,  1,  1};
//const int dx[] = {-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Moves
//const int dy[] = {-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Moves
 
const double    PI    = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int       maxn  = 1e5 + 10;
const int       maxm  = 1e6 + 10;
const int       maxk  = 5e5 + 10;
const int       LOG   = 20;
const int       base  = 311;
const int       root  = 1e9;
const int       Block = 600;
 
template <class an, class lyis>
    bool minimize(an &x, const lyis y){
        if(x > y){
            x = y;
            return true;
        } else return false;
    }
 
template <class an, class lyis>
    bool maximize(an &x, const lyis y){
        if(x < y){
            x = y;
            return true;
        } else return false;
    }
 
#define int ll
 
int n, s, d;
int a[maxn];
int res;
bool del[maxn];
 
int solve() {
    int ans = 0, cur = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
    for (int i = s; i <= n; i++) {
        q.push({a[i], -i}), cur += a[i];
        while (q.size() > 0 && i - s + q.size() > d) {
            cur -= q.top().first;
            q.pop();
        }
        ans = max(cur, ans);
    }
    while (q.size() > 0) q.pop();
    cur = 0;
    priority_queue <int> pos;
    memset(del, 0, sizeof(del));
    for (int i = s; i <= n; i++) {
        q.push({a[i], -i}), pos.push(i), cur += a[i];
        while (q.size() > 0 && i - s + q.size() > d) {
            pair <int, int> x = q.top();
            q.pop();
            cur -= x.first;
            del[-x.second] = 1;
        }
        if (cur == ans) break;
    }
    while (pos.size() > 0) {
        int x = pos.top();
        if (del[x]) pos.pop(), del[x] = 0;
        else break;
    }
    for (int i = s - 1, j = d - 1; i >= 1 && j >= 1; --i, --j) {
        q.push({a[i], -i}), pos.push(i), cur += a[i];
        while (q.size() > 0 && pos.top() - i + q.size() > j) {
            pair <int, int> x = q.top();
            q.pop();
            cur -= x.first;
            del[-x.second] = 1;
            while (pos.size() > 0) {
                int x = pos.top();
                if (del[x]) pos.pop(), del[x] = 0;
                else break;
            }
        }
        ans = max(cur, ans);
    }
    maximize(res, ans);
}
 
void init() {
    cin >> n >> s >> d;
    ++s;
    for (int i = 1; i <= n; i++) cin >> a[i];
}
 
int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t attraction[]) {
  s = S;
  d = D;
  n = N;
  for (int i = 1; i <= n; i++) a[i] = attraction[i - 1];
  ++s;
    solve();
    reverse(a + 1, a + n + 1);
    s = n - s + 1;
    solve();
    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'll solve()':
holiday.cpp:70:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   70 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:82:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   82 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:97:57: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   97 |         while (q.size() > 0 && pos.top() - i + q.size() > j) {
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:111:1: warning: no return statement in function returning non-void [-Wreturn-type]
  111 | }
      | ^

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