oj.uz

Submission #582289

# Submission time Handle Problem Language Result Execution time Memory
582289 2022-06-23T15:38:30 Z Josia Holiday (IOI14_holiday) C++14
47 / 100
 4869 ms 1236 KB 
#include <bits/stdc++.h>
#include"holiday.h"

using namespace std;


long long int findFromZero(int n, int start, int d, int attraction[], int walkingFactor) {
    assert(start == 0);
    map<int, int> bestAttractions;
    long long int res = 0;
    long long int sum = 0;
    int inUse = 0;
    for (int i = 0; i<min(d, n); i++) {
        sum += attraction[i]; bestAttractions[attraction[i]]++; inUse++;

        while (i*walkingFactor + inUse > d) {
            if (bestAttractions.empty()) return res;
            sum -= (*bestAttractions.begin()).first; bestAttractions[(*bestAttractions.begin()).first]--; inUse--;
            if (bestAttractions[(*bestAttractions.begin()).first] == 0) bestAttractions.erase((*bestAttractions.begin()).first);
        }
        // cerr << i << " " << inUse << "\n";

        res = max(sum, res);
    }

    return res;
}


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (n > 3000) {
        return findFromZero(n, start, d, attraction, 1);
    }



    vector<int> left;
    vector<int> right;

    for (int i = 0; i<n; i++) {
        if (i<=start) left.push_back(attraction[i]);
        if (i>start) right.push_back(attraction[i]);
    }

    reverse(left.begin(), left.end());

    int attL[left.size()];
    int attR[right.size()];

    for (int i = 0; i<left.size(); i++) attL[i] = left[i];
    for (int i = 0; i<right.size(); i++) attR[i] = right[i];

    long long int res = 0;
    for (int i = 0; i<=d; i++) {
        long long int tmp = 0;
        tmp += findFromZero(left.size(), 0, i, attL, 1);
        tmp += findFromZero(right.size(), 0, d-i-2, attR, 2);
        res = max(res, tmp);

        tmp = 0;
        tmp += findFromZero(left.size(), 0, i, attL, 2);
        tmp += findFromZero(right.size(), 0, d-i-1, attR, 1);
        res = max(res, tmp);
    }


    return res;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i<left.size(); i++) attL[i] = left[i];
      |                     ~^~~~~~~~~~~~
holiday.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i<right.size(); i++) attR[i] = right[i];
      |                     ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 692 KB Output is correct
5 Correct 1 ms 608 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 684 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 9 ms 688 KB Output is correct
5 Correct 11 ms 684 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 8 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4869 ms 1064 KB Output is correct
2 Correct 191 ms 740 KB Output is correct
3 Correct 3135 ms 996 KB Output is correct
4 Correct 1839 ms 844 KB Output is correct
5 Correct 1602 ms 1024 KB Output is correct
6 Correct 88 ms 704 KB Output is correct
7 Correct 39 ms 596 KB Output is correct
8 Correct 43 ms 596 KB Output is correct
9 Correct 28 ms 700 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 1236 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -