oj.uz

Submission #897532

# Submission time Handle Problem Language Result Execution time Memory
897532 2024-01-03T11:00:24 Z ThylOne Rice Hub (IOI11_ricehub) C++14
0 / 100
 1000 ms 2008 KB 
#include "ricehub.h"
#include<bits/stdc++.h>

using namespace std;
using pll = pair<long long,long long>;
vector<pll> pos;
long long budget;
int limit;
bool existWithT(int T){
  long long sum = 0;
  int taille = 0;
  int right=0;
  for(int left=0;left<pos.size();left++){
    while(taille<T && right<pos.size()){
      taille+=pos[right].second;
      sum+=pos[right].first*pos[right].second;
      right++;
    }
    if(taille<T)break;
    double bestInf = double(sum)/double(taille);
    double bestSup = ceil(double(sum)/double(taille));
    auto scoring = [&](int x){
      long long re = 0;
      for(int i=left;i<=min(right,(int)pos.size()-1);i++)
        re+=pos[i].second * abs(x-pos[i].first);
      return re;
    };
    if(scoring(bestInf)<=budget || scoring(bestSup)<=budget)return true;
    taille-=pos[left].second;
    sum-=pos[left].first*pos[left].second;
  }
  return false;
}
int besthub(int R, int L, int X[], long long B)
{

  budget = B;
  
  limit = L;
  map<int,int> occ;
  for(int i = 0;i<R;i++){
    occ[X[i]]++;
  }
  for(int i = 0;i<R;i++){
    if(occ[X[i]])
      pos.push_back({X[i],occ[X[i]]});
    occ[X[i]]=0;
  }
  sort(pos.begin(),pos.end());
  for(int i=R;i>=1;i--){
    if(existWithT(i)){
      return i;
    }
  }
}

Compilation message

ricehub.cpp: In function 'bool existWithT(int)':
ricehub.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int left=0;left<pos.size();left++){
      |                  ~~~~^~~~~~~~~~~
ricehub.cpp:14:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while(taille<T && right<pos.size()){
      |                       ~~~~~^~~~~~~~~~~
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:40:16: warning: control reaches end of non-void function [-Wreturn-type]
   40 |   map<int,int> occ;
      |                ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 448 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Incorrect 0 ms 360 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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