Submission #597045

#	Time	Username	Problem	Language	Result	Execution time	Memory
597045		PiejanVDC	Horses (IOI15_horses)	C++17	17 / 100	1591 ms	12256 KiB

horses

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

vector<long long>x,y;

long long mod = (long long)1000000007;

int init(int n, int X[], int Y[]) {
    for(int i = 0 ; i < n ; i++)
        x.push_back(X[i]), y.push_back(Y[i]);
    int last = -1;
    long long got = 1;
    long long ans = 0;
    long long curr = 0;
    long long prev = -1;

    while(last < n-1) {
        for(int i = last+1 ; i < n ; i++) {
             got *= x[i];
             got %= mod;
             if((y[i]%mod * (got-1)%mod)%mod > prev%mod)
                last = i, prev = y[i] * (got-1);
            prev %= mod;
             // + case where you sell all of them
            ans = max(ans, (curr%mod + (y[i]%mod * got%mod)%mod)%mod);
            ans %= mod;
        }
        curr += prev;
        curr %= mod;
        prev = -1;
        got = 1;
    }

    ans = max(ans, curr);
    assert(ans >= 0);
    return ans%mod;
}

int updateX(int p, int val) {
    int n = (int)x.size();
    x[p] = val;

    int last = -1;
    long long got = 1;
    long long ans = 0;
    long long curr = 0;
    long long prev = -1;

    while(last < n-1) {
        for(int i = last+1 ; i < n ; i++) {
             got *= x[i];
             got %= mod;
             if((y[i]%mod * (got-1)%mod)%mod > prev%mod)
                last = i, prev = y[i] * (got-1);
            prev %= mod;
             // + case where you sell all of them
            ans = max(ans, (curr%mod + (y[i]%mod * got%mod)%mod)%mod);
            ans %= mod;
        }
        curr += prev;
        curr %= mod;
        prev = -1;
        got = 1;
    }

    ans = max(ans, curr);
    assert(ans >= 0);
    return ans%mod;
}

int updateY(int p, int val) {
    int n = (int)x.size();
    y[p] = val;

    int last = -1;
    long long got = 1;
    long long ans = 0;
    long long curr = 0;
    long long prev = -1;

    while(last < n-1) {
        for(int i = last+1 ; i < n ; i++) {
             got *= x[i];
             got %= mod;
             if((y[i]%mod * (got-1)%mod)%mod > prev%mod)
                last = i, prev = y[i] * (got-1);
            prev %= mod;
             // + case where you sell all of them
            ans = max(ans, (curr%mod + (y[i]%mod * got%mod)%mod)%mod);
            ans %= mod;
        }
        curr += prev;
        curr %= mod;
        prev = -1;
        got = 1;
    }

    ans = max(ans, curr);
    assert(ans >= 0);
    return ans%mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:37:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |     return ans%mod;
      |            ~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:69:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |     return ans%mod;
      |            ~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:101:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |     return ans%mod;
      |            ~~~^~~~

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