제출 #1241397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241397		mychecksedad	추월 (IOI23_overtaking)	C++17	39 / 100	3595 ms	12112 KiB

overtaking

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


ll dp[N][N];
int n, m;
vi W, S;
vector<ll> T;
void init(int L, int nn, std::vector<long long> TT, std::vector<int> WW, int X, int mm, std::vector<int> SS)
{
  S = SS;
  W = WW;
  T = TT;
  n = nn;
  m = mm;
  W.pb(X);
  return;
}

long long arrival_time(long long Y)
{
  T.pb(Y);
  for(int i = 0; i <= n; ++i) dp[0][i] = T[i];
  for(int i = 1; i < m; ++i){
    ll dif = S[i] - S[i - 1];
    vector<pair<ll, int>> q;
    for(int j = 0; j <= n; ++j) q.pb({dp[i-1][j], j});
    sort(all(q));
    ll last = 0ll, last2 = 0ll;
    for(int j = 0; j <= n; ++j){
      int p = q[j].ss;
      dp[i][p] = max(last, dp[i - 1][p] + dif * W[p]);
      last2 = max(last2, dp[i][p]);
      if(j + 1 <= n && q[j+1].ff != q[j].ff) last=max(last,last2);
    }
    // for(int j = 0; j <= n; ++j){
      // cerr << dp[i][j] << ' ';
    // }
    // cerr << '\n';
  }
  T.pop_back();
  return dp[m-1][n];
}

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