Submission #35303

#	Time	Username	Problem	Language	Result	Execution time	Memory
35303		andremfq	Cultivation (JOI17_cultivation)	C++14	0 / 100	99 ms	7024 KiB

cultivation

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
const int MAXM = 100010;
int n, m;
long long t[MAXN];
long long s[MAXN];
long long f[MAXM];
long long dp[MAXM];

// int pointer; //Keeps track of the best line from previous query
vector<long long> M; //Holds the slopes of the lines in the envelope
vector<long long> B; //Holds the y-intercepts of the lines in the envelope
//Returns true if either line l1 or line l3 is always better than line l2
bool bad(int l1,int l2,int l3)
{
  /*
  intersection(l1,l2) has x-coordinate (b1-b2)/(m2-m1)
  intersection(l1,l3) has x-coordinate (b1-b3)/(m3-m1)
  set the former greater than the latter, and cross-multiply to
  eliminate division
  */
  return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]);
}
//Adds a new line (with lowest slope) to the structure
void add(long long m,long long b)
{
  //First, let's add it to the end
  M.push_back(m);
  B.push_back(b);
  //If the penultimate is now made irrelevant between the antepenultimate
  //and the ultimate, remove it. Repeat as many times as necessary
  while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
  {
    M.erase(M.end()-2);
    B.erase(B.end()-2);
  }
}
double iniline(int p){
  if(p == 0) return -1000000000000000;
  return (double (B[p-1]-B[p]))/(M[p]-M[p-1]);
}
//Returns the minimum y-coordinate of any intersection between a given vertical
//line and the lower envelope
long long query(double x, long long f1, long long f2)
{
  /*//If we removed what was the best line for the previous query, then the
  //newly inserted line is now the best for that query
  if (pointer>=M.size())
    pointer=M.size()-1;
  //Any better line must be to the right, since query values are
  //non-decreasing
  while (pointer<M.size()-1&&
    M[pointer+1]*x+B[pointer+1]<M[pointer]*x+B[pointer])
    pointer++;
  return M[pointer]*x+B[pointer];*/

  int ini = 0;
  int fim = M.size()-1;

  while(fim>ini){
    int med = (ini+fim)/2;
    if(ini == fim-1) med = fim;
    double aux = iniline(med);
    if(x < aux){
      fim = med-1;
    } else {
      ini = med;
    }
  }
  return f1*M[ini]+f2*B[ini];
}


int main(){
  scanf("%d%d", &n,&m);
  s[0]=0;
  for(int i=1; i<=n; i++) {
    scanf("%lld", &t[i]); 
    s[i]=t[i]+s[i-1];
    add(s[i], -s[i-1]);
  }
  // printf("oi\n");
  for(int j=1; j<=m; j++) {
    scanf("%lld", &f[j]);
    dp[j] = dp[j-1] + query(((double)f[j-1])/f[j], f[j-1], f[j]);
    // printf("dp[%d] = %lld\n", j, dp[j]);
  }
  printf("%lld\n", dp[m]+f[m]*s[n]);
  return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:78:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n,&m);
                       ^
cultivation.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t[i]); 
                         ^
cultivation.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &f[j]);
                         ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20