제출 #1241385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241385		noyancanturk	Overtaking (IOI23_overtaking)	C++20	65 / 100	3593 ms	14916 KiB

overtaking

#include "overtaking.h"

#include<bits/stdc++.h>
using namespace std;

const int lim=1100;

using mint=long long;
using pii=pair<mint,mint>;

mint dp[lim][lim];

int n,m,x;

vector<mint>t;
vector<int>w,s;
int p[lim][lim];

void init(int L,int N,vector<mint>T,vector<int>W,int X,int M,vector<int> S)
{   
  n=N,m=M,x=X;
  t=T,w=W,s=S;
  for(int i=0;i<n;i++){
    dp[0][i]=t[i];
  }
  for(int i=0;i+1<m;i++){
    iota(p[i],p[i]+n,0);
    sort(p[i],p[i]+n,[&](int i1,int i2)->bool {
      if(dp[i][i1]^dp[i][i2])return dp[i][i1]<dp[i][i2];
      return w[i1]<w[i2];
    });
    for(int j=0;j<n;j++){
      dp[i+1][j]=dp[i][j]+1ll*w[j]*(s[i+1]-s[i]);
    }
    for(int j=1;j<n;j++){
      dp[i+1][p[i][j]]=max(dp[i+1][p[i][j]],dp[i+1][p[i][j-1]]);
    }
  }
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<m;j++){
  //     cerr<<dp[j][i]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  return;
}

mint arrival_time(mint y)
{
  for(int i=0;i+1<m;i++){
    int l=0,r=n-1,res=-1;
    while(l<=r){
      int mid=l+r>>1;
      if(y==dp[i][p[i][mid]]){
        if(w[p[i][mid]]<x){
          l=mid+1;
          res=mid;
        }else{
          r=mid-1;
        }
      }else if(dp[i][p[i][mid]]<y){
        l=mid+1;
        res=mid;
      }else{
        r=mid-1;
      }
    }
    y+=1ll*x*(s[i+1]-s[i]);
    if(res!=-1){
      y=max(y,dp[i+1][p[i][res]]);
    }
  }
  return y;
}

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