oj.uz

Submission #427027

# Submission time Handle Problem Language Result Execution time Memory
427027 2021-06-14T11:53:55 Z ollel Horses (IOI15_horses) C++17
17 / 100
 1500 ms 15948 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 288 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 292 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 308 KB Output isn't correct
22 Halted 0 ms 0 KB -