oj.uz

Submission #242454

# Submission time Handle Problem Language Result Execution time Memory
242454 2020-06-27T17:52:10 Z joseacaz Holiday (IOI14_holiday) C++17
47 / 100
 5000 ms 2072 KB 
#include"holiday.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;


ll findMaxAttraction(int N, int start, int d, int a[])
{
    int k;
    ll ans = 0, sum = 0;
    priority_queue<ll> PQ;
    //only right
    if(start == 0)
    {
        k = d;
        for(int j = 0; j < N; j++)
        {
            sum += a[j];
            PQ.push(-a[j]);
            while(PQ.size() > k)
            {
                sum += PQ.top();
                PQ.pop();
            }
            ans = max(ans, sum);
            //cerr << i << " " << j << " " << sum << "\n";
            k--;
            if(k < 0)
                break;
        }
        return ans;
    }

    //first left then right
    for(int i = start; i >= 0; i--)
    {
        k = d - (start - i);
        sum = 0;
        while(!PQ.empty())
            PQ.pop();
        //cerr << k << "\n";
        for(int j = i; j < N; j++)
        {
            sum += a[j];
            PQ.push(-a[j]);
            while(PQ.size() > k)
            {
                sum += PQ.top();
                PQ.pop();
            }
            ans = max(ans, sum);
            //cerr << i << " " << j << " " << sum << "\n";
            k--;
            if(k < 0)
                break;
        }
    }

    //first right then left
    for(int i = start; i < N; i++)
    {
        k = d - (i - start);
        sum = 0;
        while(!PQ.empty())
            PQ.pop();
        //cerr << k << "\n";
        for(int j = i; j >= 0; j--)
        {
            sum += a[j];
            PQ.push(-a[j]);
            while(PQ.size() > k)
            {
                sum += PQ.top();
                PQ.pop();
            }
            //cerr << i << " " << j << " " << sum << "\n";
            ans = max(ans, sum);
            k--;
            if(k < 0)
                break;
        }
    }

    return ans;
}

Compilation message

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:30:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(PQ.size() > k)
                   ~~~~~~~~~~^~~
holiday.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(PQ.size() > k)
                   ~~~~~~~~~~^~~
holiday.cpp:81:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(PQ.size() > k)
                   ~~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1912 KB Output is correct
2 Correct 16 ms 2040 KB Output is correct
3 Correct 19 ms 2040 KB Output is correct
4 Correct 16 ms 2072 KB Output is correct
5 Correct 24 ms 1532 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 13 ms 1276 KB Output is correct
8 Correct 17 ms 1404 KB Output is correct
9 Correct 8 ms 896 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 384 KB Output is correct
2 Correct 128 ms 436 KB Output is correct
3 Correct 307 ms 384 KB Output is correct
4 Correct 488 ms 384 KB Output is correct
5 Correct 386 ms 384 KB Output is correct
6 Correct 25 ms 256 KB Output is correct
7 Correct 20 ms 384 KB Output is correct
8 Correct 22 ms 256 KB Output is correct
9 Correct 22 ms 256 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5034 ms 1356 KB Time limit exceeded
2 Halted 0 ms 0 KB -