oj.uz

Submission #50985

# Submission time Handle Problem Language Result Execution time Memory
50985 2018-06-15T11:21:34 Z Talant Holiday (IOI14_holiday) C++17
47 / 100
 5000 ms 5620 KB 
#include"holiday.h"

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);

long long ans;
int u[N];

multiset<int> st;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
      if (start == 0 && n > 3000) {
            for (int i = 0; i < n; i ++) {
                  u[attraction[i]] ++;

                  int cn = d - i;

                  if (cn <= 0)
                        continue;

                  long long sum = 0;


                  for (int j = 100; j >= 1; j --) {
                        int o = min(u[j],cn);
                        sum += (o * 1ll * j);
                        cn -= o;
                  }
                  ans = max(ans,sum);
            }
            return ans;
      }
      else {
            for (int i = 0; i <= start; i ++) {
                  st.clear();
                  long long sum = 0;
                  for (int j = i; j < n; j ++) {
                        st.insert(attraction[j]);
                        sum += attraction[j];

                        int dist = 0;
                        if (j <= start) dist = d - (start - i);
                        else if (start <= i) dist = d - (j - start);
                        else dist = d - ((abs(start - i) + abs(j - start)) + min(abs(start - i),abs(j - start)));

                        if (dist <= 0)
                              break;
                        while (!st.empty() && st.size() > dist) {
                              sum -= (*st.begin());
                              st.erase(st.begin());
                        }
                        ans = max(ans,sum);
                  }
            }
            return ans;
      }
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:56:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         while (!st.empty() && st.size() > dist) {
                                               ~~~~~~~~~~^~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 904 KB Output is correct
2 Correct 29 ms 904 KB Output is correct
3 Correct 34 ms 924 KB Output is correct
4 Correct 29 ms 924 KB Output is correct
5 Correct 33 ms 924 KB Output is correct
6 Correct 9 ms 924 KB Output is correct
7 Correct 18 ms 924 KB Output is correct
8 Correct 20 ms 924 KB Output is correct
9 Correct 8 ms 924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 924 KB Output is correct
2 Correct 342 ms 924 KB Output is correct
3 Correct 345 ms 924 KB Output is correct
4 Correct 288 ms 924 KB Output is correct
5 Correct 494 ms 924 KB Output is correct
6 Correct 7 ms 924 KB Output is correct
7 Correct 16 ms 924 KB Output is correct
8 Correct 24 ms 924 KB Output is correct
9 Correct 26 ms 924 KB Output is correct

Subtask #4
0 / 53.0

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