Submission #861713

#	Time	Username	Problem	Language	Result	Execution time	Memory
861713		gurkot	Overtaking (IOI23_overtaking)	C++17	65 / 100	3501 ms	39248 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,x;
pair <long long, int> tmp[1001];
long long t[1001][1001]; int w[1001][1001];
int s[1001];

void init(int L, int N, std::vector<long long> T, std::vector<int> W, 
          int X, int M, std::vector<int> S) {
 n=0; m=M; x=X; 
 
 for (int i=0;i<N;i++){
  tmp[i].first=T[i]; tmp[i].second=W[i];
 }
 
 sort(tmp,tmp+N);
 
 for (int i=0;i<N;i++) {
  T[i]=tmp[i].first; W[i]=tmp[i].second;
 }
  
 for (int i=0;i<M;i++) s[i]=S[i];
 int nom;
 
 for (int i=0;i<N;i++)
  if (W[i]>X) {
  	w[0][n]=W[i];t[0][n]=T[i];
  	nom=n;
  	while (nom>0) 
	 if (t[0][nom]==t[0][nom-1] && w[0][nom]<w[0][nom-1])
  	  {swap(t[0][nom],t[0][nom-1]);swap(w[0][nom],w[0][nom-1]);nom--;}
  	 else break; 
  	n++;
  } 
  
  //counting without reserve bus (precalculation)
  for (int i=1;i<m;i++) {
   w[i][0]=w[i-1][0];
   t[i][0]=t[i-1][0]+(long long)w[i][0]*(s[i]-s[i-1]);    
  
   for (int j=1;j<n;j++){
   	w[i][j]=w[i-1][j];
   	t[i][j]=max(t[i][j-1],t[i-1][j]+(long long)w[i-1][j]*(s[i]-s[i-1]));
   	nom=j;
   	while (nom>0) 
	 if (t[i][nom]==t[i][nom-1] && w[i][nom]<w[i][nom-1])
  	  {swap(t[i][nom],t[i][nom-1]);swap(w[i][nom],w[i][nom-1]);nom--;}
  	 else break; 
   }
    
  }//i
  
 return;
}

long long arrival_time(long long Y){
 long long rt=Y;	
 int nomr=n;
 while (nomr>0)
  if (rt<=t[0][nomr-1]) nomr--;
  else break;
 if (nomr==0) return rt+(long long)s[m-1]*x;
 
 for (int i=1;i<m;i++){
  rt=max(rt+(long long)(s[i]-s[i-1])*x,t[i][nomr-1]);
  while (nomr>0)
   if (rt==t[i][nomr-1]) nomr--;
   else break;
  if (nomr==0) return rt+(long long)(s[m-1]-s[i])*x; 
 	
 }//i  
	
 return rt;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:28:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   28 |  for (int i=0;i<N;i++)
      |  ^~~
overtaking.cpp:40:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |   for (int i=1;i<m;i++) {
      |   ^~~

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