Submission #1196511

#TimeUsernameProblemLanguageResultExecution timeMemory
1196511SSKMFAliens (IOI16_aliens)C++20
4 / 100
0 ms328 KiB
#include "aliens.h" #include <vector> #include <utility> #include <algorithm> #include <cstdint> using namespace std; pair <int64_t , int> minim[100001]; pair < pair <int , int64_t> , int > stiva[100001]; inline pair <int64_t , int> Query (int& inceput , int& sfarsit , const int punct) { while (inceput < sfarsit && stiva[inceput + 1].first.second - stiva[inceput].first.second <= 1LL * punct * (stiva[inceput].first.first - stiva[inceput + 1].first.first)) { inceput++; } return {1LL * stiva[inceput].first.first * punct + stiva[inceput].first.second , stiva[inceput].second}; } long long take_photos (int dorit , int lungime , int limita , vector <int> linie , vector<int> coloana) { vector < pair <int , int> > sir(dorit + 1); for (int indice = 0 ; indice < dorit ; indice++) { if (coloana[indice] < linie[indice]) { swap(linie[indice] , coloana[indice]); } sir[indice + 1] = {linie[indice] , coloana[indice]}; } sort(sir.begin() , sir.end()); int ramas = 1; for (int indice = 2 ; indice <= dorit ; indice++) { if (sir[ramas].first == sir[indice].first) { sir[ramas].second = sir[indice].second; } else if (sir[ramas].second < sir[indice].second) { sir[++ramas] = sir[indice]; } } sir.resize(ramas + 1); dorit = ramas; limita = min(limita , dorit); for (int indice = 1 ; indice <= dorit ; indice++) { minim[indice] = {100000000000000000LL , 0}; } sir[0] = {-1 , -1}; int64_t inceput = 0 , sfarsit = 100000LL , rezultat = 0; while (inceput <= sfarsit) { int __stanga = 1 , __dreapta = 0; const int64_t cost = (inceput + sfarsit) / 2; for (int dreapta = 1 ; dreapta <= dorit ; dreapta++) { pair < pair <int , int64_t> , int > candidat = {{ -2 * (sir[dreapta].first - 1) , minim[dreapta - 1].first + 1LL * (sir[dreapta].first - 1) * (sir[dreapta].first - 1) - 1LL * max(0 , sir[dreapta - 1].second - sir[dreapta].first + 1) * max(0 , sir[dreapta - 1].second - sir[dreapta].first + 1) - cost } , minim[dreapta - 1].second + 1 }; while (__stanga < __dreapta && (long double)(candidat.first.second - stiva[__dreapta - 1].first.second) * (stiva[__dreapta - 1].first.first - stiva[__dreapta].first.first) < (long double)(stiva[__dreapta].first.second - stiva[__dreapta - 1].first.second) * (stiva[__dreapta - 1].first.first - candidat.first.first)) { __dreapta--; } stiva[++__dreapta] = candidat; minim[dreapta] = Query(__stanga , __dreapta , sir[dreapta].second); minim[dreapta].first += 1LL * sir[dreapta].second * sir[dreapta].second; } if (minim[dorit].second <= limita) { rezultat = minim[dorit].first - cost * limita; sfarsit = cost - 1; } else { inceput = cost + 1; } } rezultat = minim[dorit].first; return rezultat; }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...