이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3+23;
const int mod = 1000000007;
int n;
ll x[N],y[N];
ll dp[N][1005];
ll dajdp(){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= 1000; j++){
dp[i][j] = -1;
}
}
dp[0][1] = 0;
for(int i = 1; i <= n; i++){ /// nakon kraja i-te godine
for(ll j = 0; j <= 1000; j++){ /// imam j konja posle prodavanja
int nagore = (j+x[i]-1)/x[i];
nagore *= x[i];
for(ll pre = nagore; pre <= 1000; pre += x[i]){ /// koliko sam konja imao pre prodavanja
if(dp[i-1][pre/x[i]] != -1) dp[i][j] = max(dp[i][j],dp[i-1][pre/x[i]]+(pre-j)*y[i]);
}
}
}
return dp[n][0];
}
bool cmp(int i,int j){
if(i == j) return 0;
if(i < j){
ll prod = y[j];
for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
if(x[h] >= (y[i]+prod-1)/prod) return 0;
else prod *= x[h];
}
return 1;
}
else{
ll prod = y[i];
for(int h = j+1; h <= i; h++){
if(x[h] >= (y[j]+prod-1)/prod) return 1;
else prod *= x[h];
}
return 0;
}
}
ll probaj(){
vector <int> v;
for(int i = 1; i <= n; i++) v.push_back(i);
sort(v.begin(),v.end(),cmp);
int pos = v[0];
ll sol = 1;
for(int i = 1; i <= pos; i++){
sol *= x[i];
sol %= mod;
}
sol *= y[pos];
sol %= mod;
return sol;
}
vector <ll> novx,novy;
bool cmp1(int i,int j){
if(i == j) return 0;
if(i < j){
ll prod = novy[j];
for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
if(novx[h] >= (novy[i]+prod-1)/prod) return 0;
else prod *= novx[h];
}
return 1;
}
else{
ll prod = novy[i];
for(int h = j+1; h <= i; h++){
if(novx[h] >= (novy[j]+prod-1)/prod) return 1;
else prod *= novx[h];
}
return 0;
}
}
ll probaj1(){
novx = {0},novy = {0};
for(int i = 1; i <= n; i++){
novx.push_back(x[i]);
novy.push_back(y[i]);
}
int cnt = 1;
for(int i = 1; i <= n; ){ /// otarasi se jedinica u x-u, mozda ostane jedna na pocetku ali to nije problem
int j = i;
ll maxi = 0;
while(j < n && novx[j+1] == 1){
maxi = max(maxi,novy[j+1]);
j++;
}
if(j != i) novy[i] = max(novy[i],maxi);
novx[cnt] = novx[i];
novy[cnt] = novy[i];
cnt++;
i = j+1;
}
cnt--;
/// sad je dovoljno da uzmes maks za poslednjih 30
vector <int> v;
for(int i = max(1,cnt-29); i <= cnt; i++) v.push_back(i);
sort(v.begin(),v.end(),cmp1);
int pos = v[0];
ll sol = 1;
for(int i = 1; i <= pos; i++){
sol *= novx[i];
sol %= mod;
}
sol *= novy[pos];
sol %= mod;
return sol;
}
ll init(int n1,int *x1,int *y1){
n = n1;
for(int i = 1; i <= n; i++) x[i] = x1[i-1], y[i] = y1[i-1];
/*ll pr = 1,prvi = 1;
for(int i = 1; i <= n; i++){
if(x[i] > 1000/pr) prvi = 0;
else pr *= x[i];
}
if(n <= 10 && prvi){
return dajdp();
}*/
return probaj1();
}
ll updateX(int pos,int val){
pos++;
x[pos] = val;
return probaj1();
}
ll updateY(int pos,int val){
pos++;
y[pos] = val;
return probaj1();
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int a;
cin >> a;
int *prvi = (int*)malloc(sizeof(int)*a);
int *drugi = (int*)malloc(sizeof(int)*a);
for(int i = 1; i <= a; i++){
int x;
cin >> x;
prvi[i-1] = x;
}
for(int i = 1; i <= a; i++){
int x;
cin >> x;
drugi[i-1] = x;
}
cout << init(a,prvi,drugi) << endl;
cout << updateY(1,2) << endl;
}*/
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'll dajdp()':
horses.cpp:21:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
21 | int nagore = (j+x[i]-1)/x[i];
| ~~~~~~~~~~^~~~~
horses.cpp:22:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
22 | nagore *= x[i];
| ~~~~~~~^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |