Submission #427027

#	Time	Username	Problem	Language	Result	Execution time	Memory
427027		ollel	Horses (IOI15_horses)	C++17	17 / 100	1583 ms	15948 KiB

horses

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define lso(x) x&(-x)

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;

vi X, Y, T;
int n, N;

ll get() {
  if (n == 1) return (X[0] * Y[0]) % 1000000009;

  int start = n - 1;
  ll pr = X[start];
  while (pr*X[start-1] < 1e9) {
    start--;
    pr *= X[start];
    if (start == 0) break;
  }

  T.assign(n, 1);
  rep(i, start, n) {
    if (i == 0) T[i] = X[i];
    else T[i] = T[i - 1] * X[i];
  }

  ll best = 0;
  rep(i, start, n) {
    best = max(best, T[i] * Y[i]);
  }

  best = best % 1000000009;
  ll mult_prev = 1;
  rep(i, 0, start) mult_prev = (mult_prev * X[i]) % 1000000009;
  best = (best * mult_prev) % 1000000009;
  return best;
}

int init(int a, int x[], int y[]) {
  n = N = a;
  X.resize(N); Y.resize(N); T.resize(N);
  rep(i,0,N) X[i] = x[i];
  rep(i,0,N) Y[i] = y[i];
  return get();
}

int updateX(int pos, int val) {
  X[pos] = val;
  return get();
}

int updateY(int pos, int val) {
  Y[pos] = val;
  return get();
}

//
// int main() {
//   int x[] = {1, 1, 1000000000, 1000000000, 1000000000};
//   int y[] = {1, 1, 1, 1, 1000000000};
//   cout << init(5, x, y);
// }

Compilation message (stderr)

horses.cpp: In function 'll get()':
horses.cpp:21:12: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   21 |   while (pr*X[start-1] < 1e9) {
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:50:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |   return get();
      |          ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:55:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |   return get();
      |          ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:60:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   60 |   return get();
      |          ~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23