제출 #935034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935034		PagodePaiva	말 (IOI15_horses)	C++17	17 / 100	54 ms	22352 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define N 500010

using namespace std;

int n;
long long v[N][2];
long long dp[N];
const long long mod = 1e9+7;
long long p = 1;

long long binpow(long long a, long long b, long long m){
	// cout << a << ' ';
	a %= m;
	if(b == 0) return 1;
	long long t = binpow(a, b/2, m);
	if(b % 2 == 0) return (t*t) % m;
	else return ((((t*t) % m)*a) % m);
}

struct Segtree{
	long long tree[4*N];

	long long join(long long a, long long b){
		return (a*b) % mod;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = v[l][0];
			return;
		}
		int mid = (l+r) >> 1;
		build(2*node,l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void update(int node, int l, int r, int pos, long long val){
		if(l == r){
			tree[node] = val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	long long query(int node, int l, int r, int tl, int tr){
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return 1;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg;

int solve(){
	if(n <= 40){
		dp[0] = 0;
		long long res = 0;
		for(int i = 1;i <= n;i++){
			dp[i] = 0;
			long long int prod = 1;
			for(int j = i;j > 0;j--){
				prod *= v[j][0];
				dp[i] = max(dp[i], dp[j-1] + ((prod-1)*v[i][1]));
				res = max(res, dp[j-1] + prod*v[i][1]);
			}
			// cout << dp[i] << ' ';
		}
		return res % mod;
	}
	long long prod = 1;
	int fim = n;
	for(int i = n-1;i > n-40;i--){
		prod *= v[n+1][0];
		if(prod > 1e9+7) break;
		if(prod*v[fim][1] < v[i][1]){
			fim = i;
			prod = 1;
		}
	}
	return seg.query(1, 1, fim, 1, n);
}

int init(int NN, int X[], int Y[]) {
	n = NN;
	for(int i = 1;i <= n;i++){
		v[i][0] = X[i-1];
		p *= v[i][0];
		p %= mod;
		v[i][1] = Y[i-1];
	}
	seg.build(1, 1, n);
	// cout << n << ' ';
	return solve();
}

int updateX(int pos, int val) {
	v[pos+1][0] = val;
	seg.update(1, 1, n, pos+1,val);
	return solve();
}

int updateY(int pos, int val) {
	v[pos+1][1] = val;
	return solve();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int solve()':
horses.cpp:72:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   return res % mod;
      |          ~~~~^~~~~
horses.cpp:78:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   78 |   if(prod > 1e9+7) break;
      |      ^~~~
horses.cpp:84:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return seg.query(1, 1, fim, 1, n);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~

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