Submission #1004913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004913		pawned	말 (IOI15_horses)	C++17	34 / 100	1593 ms	16096 KiB

horses

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "horses.h"

const ll MOD = 1e9 + 7;
const ll MAX = 1e9 + 5;

ll norm(ll x) {
	x %= MOD;
	x += MOD;
	x %= MOD;
	return x;
}

int N;

vi X;
vi Y;

ll solve() {
	int bestp = N - 1;
	ll currn = Y[N - 1];
	ll currd = 1;
	ll bestn = currn;
	ll bestd = currd;
	for (int i = N - 2; i >= 0; i--) {
		currn = Y[i];
		currd *= X[i + 1];
		if (currd >= MAX)
			break;
		if (currn * bestd > bestn * currd) {
			bestp = i;
			bestn = currn;
			bestd = currd;
		}
	}
	ll ans = 1;
	for (int i = 0; i <= bestp; i++) {
		ans *= X[i];
		ans = norm(ans);
	}
	ans *= Y[bestp];
	ans = norm(ans);
	return ans;
}

int init(int n, int x[], int y[]) {
	N = n;
	X = vi(N); Y = vi(N);
	for (int i = 0; i < N; i++) {
		X[i] = x[i];
		Y[i] = y[i];
	}
	ll ans = solve();
	return (int)(ans);
}

int updateX(int pos, int val) {
	X[pos] = val;
	ll ans = solve();
	return (int)(ans);
}

int updateY(int pos, int val) {
	Y[pos] = val;
	ll ans = solve();
	return (int)(ans);
}

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