oj.uz

Submission #679338

# Submission time Handle Problem Language Result Execution time Memory
679338 2023-01-08T05:09:03 Z Cross_Ratio Holiday (IOI14_holiday) C++14
47 / 100
 5000 ms 1904 KB 
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
int N, st, d;
int A[100005];
typedef pair<int, int> P;
ll findMaxAttraction(int _N, int _st, int _d, int attraction[]) {
    N = _N, st = _st, d = _d;
    int i, j;
    for(i=0;i<N;i++) A[i] = attraction[i];
    ll ans = 0;
    ll sum = 0;
    for(i=st;i>=0;i--) {
        int val = d;
        val -= 2*(st - i);
        if(val <= 0) break;
        priority_queue<int, vector<int>, greater<int>> PQ;
        ll cnt = 0;
        for(int j = i; j <= st; j++) {
            cnt += A[j];
            PQ.push(A[j]);
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
        }
        ans = max(ans, cnt);
        for(j=st+1;j<N;j++) {
            cnt += A[j];
            PQ.push(A[j]);
            val--;
            if(val <= 0) break;
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
            ans = max(ans, cnt);
        }
    }
    if(st==0) return ans;
    st = N-1-st;
    reverse(A, A+N);
    for(i=st;i>=0;i--) {
        int val = d;
        val -= 2*(st - i);
        if(val <= 0) break;
        priority_queue<int, vector<int>, greater<int>> PQ;
        ll cnt = 0;
        for(int j = i; j <= st; j++) {
            cnt += A[j];
            PQ.push(A[j]);
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
        }
        ans = max(ans, cnt);
        for(j=st+1;j<N;j++) {
            cnt += A[j];
            PQ.push(A[j]);
            val--;
            if(val <= 0) break;
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
            ans = max(ans, cnt);
        }
    }
    return ans;
}

Compilation message

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:23:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:34:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:53:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:64:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:13:8: warning: unused variable 'sum' [-Wunused-variable]
   13 |     ll sum = 0;
      |        ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1616 KB Output is correct
2 Correct 8 ms 1904 KB Output is correct
3 Correct 8 ms 1824 KB Output is correct
4 Correct 8 ms 1860 KB Output is correct
5 Correct 14 ms 1608 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 9 ms 1492 KB Output is correct
9 Correct 2 ms 980 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 708 KB Output is correct
2 Correct 39 ms 716 KB Output is correct
3 Correct 49 ms 720 KB Output is correct
4 Correct 240 ms 596 KB Output is correct
5 Correct 171 ms 700 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 11 ms 704 KB Output is correct
8 Correct 12 ms 596 KB Output is correct
9 Correct 14 ms 692 KB Output is correct

Subtask #4
0 / 53.0

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