소스 코드

#include <iostream>
#include <vector>
#define endl "\n"
#define length first
#define speed second

using namespace std;

int n; // 구간 길이
int m; // 테스트 구간 길이
vector<pair<int, int>> original; // 원본 구간 정보
vector<pair<int, int>> test; // 테스트 구간 정보

void print(vector<pair<int, int>> arr) {
  for (auto pii : arr) {
    cout << pii.first << " " << pii.second << endl;
  }
}

void init() {
  cin >> n >> m;
  original = vector<pair<int, int>>(n + 1);
  test = vector<pair<int, int>>(n + 1);

  for (int i = 1; i <= n; ++i) {
    int len, spd;
    cin >> len >> spd;
    original[i].length = len;
    original[i].speed = spd;
  }

  for (int i = 1; i <= m; ++i) {
    int len, spd;
    cin >> len >> spd;
    test[i].length = len;
    test[i].speed = spd;
  }
}

void solve() {
  int ptr1 = 1;
  int ptr2 = 1;
  int maxSpeed = 0;
  
  while (ptr1 <= n && ptr2 <= m) {
    if (test[ptr2].speed > original[ptr1].speed) {
      if (maxSpeed < test[ptr2].speed - original[ptr1].speed) {
        maxSpeed = test[ptr2].speed - original[ptr1].speed;
      }
    }
    
    if (original[ptr1].length > test[ptr2].length) {
      original[ptr1].length -= test[ptr2].length;
      ++ptr2;
    }
    else if (original[ptr1].length < test[ptr2].length) {
      test[ptr2].length -= original[ptr1].length;
      ++ptr1;
    }
    else {
      ++ptr1;
      ++ptr2;
    }
  }

  cout << maxSpeed << endl;
}

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  init();

  solve();
  
  return 0;
}

해설

원본 구간에 대한 정보와 테스트 구간에 대한 정보를 투포인터를 사용하여 최고 초과 속도를 업데이트

<투포인터 이동 조건>
if 포인터1의 구간 길이 > 포인터2의 구간 길이
: 포인터1의 구간 길이 -= 포인터 2의 구간 길이
: 포인터 2 1증가

if 포인터2의 구간 길이 > 포인터1의 구간 길이
: 포인터2의 구간 길이 -= 포인터 1의 구간 길이
: 포인터 1 1증가

if 포인터1의 구간 길이 == 포인터2의 구간 길이
: 포인터 1과 포인터 2 둘 다 1씩 증가