Submission #503415

#TimeUsernameProblemLanguageResultExecution timeMemory
503415AmirElarbiHorses (IOI15_horses)C++14
17 / 100
236 ms33352 KiB
#include <bits/stdc++.h> #include "horses.h" #define vi vector<int> #define ve vector #define ll unsigned long long #define vf vector<float> #define vll vector<pair<ll,ll>> #define ii pair<int,int> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 1e9 #define eps 1e-7 #define eps1 1e-25 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 1e5+5 #define V 450 using namespace std; const int MOD = 1e9+7; ll x[500005],y[500005]; ll dp[500005],memo[500005]; int n,k; ll srch(int i, ll nb){ if(i >= n) return 0; if(dp[i]!=-1)return dp[i]; while(log10(x[i])+log10(y[i])+log10(nb) > 18){ nb/=x[k]; k++; } assert(log10(x[i])+log10(y[i])+log10(nb) <= 18); return dp[i] = max(srch(i+1,(nb*x[i])), ((nb*x[i])*y[i])); } int init(int N, int X[], int Y[]) { n = N; memset(dp,-1,sizeof dp); for (int i = 0; i < n; ++i) { x[i] = X[i]; y[i] = Y[i]; } memo[0] = 1; for (int j = 1; j <= n; ++j) { memo[j]=(memo[j-1]%MOD*x[j-1]%MOD)%MOD; } ll a = 1; k = n-1; while(a <= 1e10 && k >= 0){ a*=x[k]; k--; } k++; ll res= (srch(k,1)%MOD*memo[k]%MOD)%MOD; return res%MOD; } int updateX(int pos, int val) { x[pos] = val; ll a = 1; k = n-1; while(a <= 1e10 && k >= 0){ a*=x[k]; k--; } k++; for (int j = k; j < n; ++j) { dp[j] = -1; } ll res= (srch(k,1)%MOD*memo[k]%MOD)%MOD; return res%MOD; } int updateY(int pos, int val) { y[pos] = val; ll a = 1; k = n-1; while(a <= 1e10 && k >= 0){ a*=x[k]; k--; } k++; for (int j = k; j < n; ++j) { dp[j] = -1; } ll res= (srch(k,1)%MOD*memo[k]%MOD)%MOD; return res%MOD; }

Compilation message (stderr)

horses.cpp: In function 'long long unsigned int srch(int, long long unsigned int)':
horses.cpp:29:10: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   29 |  if(dp[i]!=-1)return dp[i];
      |     ~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:52:8: warning: conversion from 'long long unsigned int' to 'double' may change value [-Wconversion]
   52 |  while(a <= 1e10 && k >= 0){
      |        ^
horses.cpp:58:12: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   58 |  return res%MOD;
      |         ~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:65:8: warning: conversion from 'long long unsigned int' to 'double' may change value [-Wconversion]
   65 |  while(a <= 1e10 && k >= 0){
      |        ^
horses.cpp:75:12: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   75 |  return res%MOD;
      |         ~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:82:8: warning: conversion from 'long long unsigned int' to 'double' may change value [-Wconversion]
   82 |  while(a <= 1e10 && k >= 0){
      |        ^
horses.cpp:92:12: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   92 |  return res%MOD;
      |         ~~~^~~~
#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...