| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1247575 | nvujica | Beech Tree (IOI23_beechtree) | C++20 | 0 ms | 0 KiB |
#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 1005;
ll e[maxn][maxn];
ll t[maxn][maxn];
vector<ll> s;
vector<ll> w;
void init(int l, int n, vector<ll> poc, vector<int> W, int X, int m, vector<int> S){
for(int i = 0; i < n; i++) t[i][0] = poc[i];
for(auto x: S) s.push_back(x);
for(auto x: W) w.push_back(x);
w.push_back(X);
return;
}
ll arrival_time(ll y){
int m = s.size();
int n = w.size() - 1;
// cout << endl;
// cout << "m: " << m << endl;
// cout << "n: " << n << endl;
t[n][0] = y;
// for(int i = 0; i <= n; i++){
// cout << t[i][0] << ' ';
// }
// cout << endl;
queue<int> q;
vector <pair<ll, int> > v;
for(int j = 1; j < m; j++){
v.clear();
for(int i = 0; i <= n; i++){
e[i][j] = t[i][j - 1] + w[i] * (s[j] - s[j - 1]);
v.push_back({t[i][j - 1], i});
}
sort(v.begin(), v.end());
// cout << "TU: ";
ll naj = 0;
for(int i = 0; i <= n; i++){
ll vri = v[i].fi;
int ind = v[i].se;
// cout << ind << ' ';
if(!i || vri != v[i - 1].fi){
// cout << "da " << ind << endl;
while(!q.empty()){
int x = q.front();
q.pop();
naj = max(naj, e[x][j]);
// cout << endl << ind << ' ' << x << endl;
}
q.push(ind);
}
else {
q.push(ind);
}
t[ind][j] = max(naj, e[ind][j]);
}
// cout << endl;
while(!q.empty()) q.pop();
// for(int i = 0; i <= n; i++){
// cout << t[i][j] << ' ';
// }
// cout << endl;
}
return t[n][m - 1];
}