제출 #411515

#제출 시각아이디문제언어결과실행 시간메모리
411515losmi247말 (IOI15_horses)C++14
17 / 100
1589 ms8524 KiB
#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; } 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 probaj(); } ll updateX(int pos,int val){ pos++; x[pos] = val; return probaj(); } ll updateY(int pos,int val){ pos++; y[pos] = val; return probaj(); } /*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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...