Submission #1061686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061686		mychecksedad	Overtaking (IOI23_overtaking)	C++17	39 / 100	3565 ms	8412 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3005;
const ll INF = 1e18;


vector<ll> T, W, S;
int n, m, x, L;
void init(int Ll, int nn, std::vector<long long> t, std::vector<int> w, int xx, int mm, std::vector<int> s)
{ 
  L = Ll, n=nn, m=mm, T=t, x=xx;
  for(int x: w) W.pb(x);
  for(int x: s) S.pb(x);
  W.pb(x);
  S.pb(Ll);
  return;
}

long long arrival_time(long long Y)
{
  T.pb(Y);
  vector<pair<ll, int>> F;
  for(int i =0; i<= n; ++i) F.pb({W[i], i});
  sort(all(F));
  reverse(all(F));
  // for(int j = 0; j <= n; ++j) cout << F[j].ff << ' ';
  vector<vector<ll>> dp(n + 2, vector<ll>(m + 2));
// cout << '\n';

  // for(int i = 0; i <= n; ++i) dp[i][0] = T[F[i].ss];
  // for(int j = 1; j <= m; ++j){
  //   ll mx = 0;
  //   vector<ll> pref(n+1);
  //   int last = 0;
  //   for(int i = 0; i <= n; ++i){
  //     if(i > 0) if(T[F[i].ss] != T[i - 1].ff) last = i - 1;
  //     dp[i][j] = max(dp[i][j - 1] + (S[j] - S[j - 1]) * F[i].ff, pref[last]);
  //     pref[i] = max(i == 0 ? 0ll : pref[i - 1], dp[i][j]);
  //   }
  // }
  for(int i = 0; i <= n; ++i){
    dp[i][0] = T[F[i].ss];
    for(int j = 1; j <= m; ++j){
      // dp[i][j] = ---;
      ll mx = dp[i][j - 1] + F[i].ff * (S[j] - S[j-1]);
      for(int i2 = 0; i2 < i; ++i2){
        if(dp[i2][j - 1] < dp[i][j - 1]) mx=max(mx, dp[i2][j]);
      }
      dp[i][j]=mx;
    }
  }
  // for(int i = 0; i <= m; ++i){
  //   for(int j = 0; j <= n; ++j) cout << dp[j][i] << ' ';
  //   cout << '\n';
  // }
  // cout << '\n';


  T.pop_back();
  int idx;
  for(int i = 0; i <= n; ++i) if(F[i].ss == n) idx = i;
  return dp[idx][m];
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:68:16: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |   return dp[idx][m];
      |                ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35