# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1205004 | PagodePaiva | 참나무 (IOI23_beechtree) | C++20 | 0 ms | 0 KiB |
#include "overtaking.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll l, n;
vector <ll> t;
vector <ll> w;
ll x, m;
vector <ll> s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
l = L;
n = N;
t = T;
x = X;
for(auto valor : W)
w.push_back(valor);
m = M;
for(auto valor : S)
s.push_back(valor);
return;
}
const int N = 1010;
ll tt[N][N];
ll e[N][N];
long long arrival_time(long long Y){
t.push_back(Y);
w.push_back(x);
for(int i = 0;i <= n;i++){
tt[i][0] = t[i];
}
for(int j = 1;j < m;j++){
vector <array <ll, 3>> v;
for(int i = 0;i <= n;i++){
e[i][j] = tt[i][j-1] + (s[j]-s[j-1])*w[i];
v.push_back({tt[i][j-1], e[i][j], i});
}
sort(v.begin(), v.end());
ll res = 0;
for(auto [tmp, exp, i] : v){
//cout << tmp << ' ' << exp << ' ' << i << '\n';
res = max(res, exp);
tt[i][j] = res;
}
//cout << '\n';
}
ll ans = tt[n][m-1];
t.pop_back();
w.pop_back();
return ans;
}