YEZAELP

PROG-1159: จัดลำดับการทดลอง (schedule)

Oct 27th, 2021
979
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. const int N = 1e3 + 10;
  6. const int M = 6e2 + 10;
  7. int day[N][N], tim[N][N];
  8. int qsA[N], qsB[N], minA[N], minB[N];
  9. int n, m;
  10.  
  11. int SumA(int i, int j){
  12.     return qsA[j] - qsA[i-1];
  13. }
  14.  
  15. int SumB(int i, int j){
  16.     return qsB[j] - qsB[i-1];
  17. }
  18.  
  19. void Solve(int a, int b, int cur_day, int cur_time){
  20.     if(cur_day < day[a][b]){
  21.         day[a][b] = cur_day;
  22.         tim[a][b] = cur_time;
  23.     }
  24.     else if(cur_day == day[a][b]){
  25.         tim[a][b] = min(tim[a][b], cur_time);
  26.     }
  27. }
  28.  
  29. int MinA(int idx){
  30.     int r = idx, l = 1, mn = idx;
  31.     while(l <= r){
  32.         int mid = (l + r) / 2;
  33.         if(SumA(mid, idx) <= m){
  34.             mn = min(mn, mid);
  35.             r = mid - 1;
  36.         }
  37.         else{
  38.             l = mid + 1;
  39.         }
  40.     }
  41.     return mn;
  42. }
  43.  
  44. int MinB(int idx){
  45.     int r = idx, l = 1, mn = idx;
  46.     while(l <= r){
  47.         int mid = (l + r) / 2;
  48.         if(SumB(mid, idx) <= m){
  49.             mn = min(mn, mid);
  50.             r = mid - 1;
  51.         }
  52.         else{
  53.             l = mid + 1;
  54.         }
  55.     }
  56.     return mn;
  57. }
  58.  
  59. int main(){
  60.  
  61.     scanf("%d%d", &m, &n);
  62.  
  63.     for(int i=1;i<=n;i++){
  64.         scanf("%d", &qsA[i]);
  65.         qsA[i] += qsA[i-1];
  66.         minA[i] = MinA(i);
  67.     }
  68.     for(int i=1;i<=n;i++){
  69.         scanf("%d", &qsB[i]);
  70.         qsB[i] += qsB[i-1];
  71.         minB[i] = MinB(i);
  72.     }
  73.  
  74.     for(int a=0;a<=n;a++){
  75.         for(int b=0;b<=n;b++){
  76.             if(a == 0 and b == 0) continue;
  77.             day[a][b] = tim[a][b] = INF;
  78.             if(a > 0){
  79.                 /// A
  80.                 for(int ia=minA[a];ia<=a;ia++){
  81.                     int cur_day = 1 + day[ia - 1][b];
  82.                     int cur_time = SumA(ia, a);
  83.                     Solve(a, b, cur_day, cur_time);
  84.                 }
  85.             }
  86.             if(b > 0){
  87.                 /// B
  88.                 for(int ib=minB[b];ib<=b;ib++){
  89.                     int cur_day = 1 + day[a][ib - 1];
  90.                     int cur_time = SumB(ib, b);
  91.                     Solve(a, b, cur_day, cur_time);
  92.                 }
  93.             }
  94.             if(a > 0 and b > 0){
  95.                 /// A & B
  96.                 int ib = b + 1;
  97.                 for(int ia=minA[a];ia<=a;ia++){
  98.                     while(SumA(ia, a) + SumB(ib - 1, b) <= m and 1 < ib){
  99.                         ib --;
  100.                     }
  101.                     int cur_day = 1 + day[ia - 1][ib - 1];
  102.                     int cur_time = SumA(ia, a) + SumB(ib, b);
  103.                     Solve(a, b, cur_day, cur_time);
  104.                 }
  105.             }
  106.         }
  107.     }
  108.  
  109.     printf("%d\n%d", day[n][n], tim[n][n]);
  110.  
  111.     return 0;
  112. }
RAW Paste Data