oj.uz

Submission #856388

# Submission time Handle Problem Language Result Execution time Memory
856388 2023-10-03T09:56:07 Z yuricon Holiday (IOI14_holiday) C++17
47 / 100
 270 ms 1752 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N = 1e5 + 6;
int n, s, d, a[N];
ll sub2()
{
    priority_queue <int, vector <int>, greater <int>> pq;
    ll sum = 0, ans = 0;
    int cnt = 0;
    for(int i = s; i < n; ++i)
    {
        sum += a[i];
        cnt++;
        pq.push(a[i]);
        while(!pq.empty() && cnt + i - s > d)
        {
            sum -= pq.top();
            pq.pop();
            cnt--;
        }
        ans = max(ans, sum);
    }
    return ans;
}
ll sub3()
{
    ll ans = 0;
    for(int i = 0; i < n; ++i)
    {
        int c = d - abs(s - i);
        if(i <= s)
        {
            priority_queue <int, vector <int>, greater <int> > pq;
            ll sum = 0;
            int cnt = 0;
            for(int j = i; j < n; ++j)
            {
                sum += a[j];
                cnt++;
                pq.push(a[j]);
                while(!pq.empty() && cnt + j - i > c)
                {
                    sum -= pq.top();
                    pq.pop();
                    cnt--;
                }
                ans = max(ans, sum);
            }
        }
        if(i >= s)
        {
            priority_queue <int, vector <int>, greater <int> > pq;
            ll sum = 0;
            int cnt = 0;
            for(int j = i; j >= 0; --j)
            {
                sum += a[j];
                cnt++;
                pq.push(a[j]);
                while(!pq.empty() && cnt + (i - j) > c)
                {
                    sum -= pq.top();
                    pq.pop();
                    cnt--;
                }
                ans = max(ans, sum);
            }
        }
    }
    return ans;
}
long long int findMaxAttraction(int na, int sa, int da, int aa[]) {
    n = na;
    s = sa;
    d = da;
    for(int i = 0; i < n; ++i)
    {
        a[i] = aa[i];
    }
    if(n <= 3000)
    {
        return sub3();
    }
    return sub2();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 856 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1752 KB Output is correct
2 Correct 6 ms 1752 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 7 ms 1752 KB Output is correct
5 Correct 12 ms 1468 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 5 ms 1340 KB Output is correct
8 Correct 8 ms 1372 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 856 KB Output is correct
2 Correct 20 ms 748 KB Output is correct
3 Correct 38 ms 860 KB Output is correct
4 Correct 270 ms 832 KB Output is correct
5 Correct 204 ms 604 KB Output is correct
6 Correct 14 ms 600 KB Output is correct
7 Correct 14 ms 604 KB Output is correct
8 Correct 16 ms 604 KB Output is correct
9 Correct 16 ms 836 KB Output is correct

Subtask #4
0 / 53.0

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