QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204036#4931. Comic BingemaghrabyJr_#WA 4ms84340kbC++203.1kb2023-10-07 00:19:542023-10-07 00:19:55

Judging History

你现在查看的是最新测评结果

  • [2023-10-07 00:19:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:84340kb
  • [2023-10-07 00:19:54]
  • 提交

answer

#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long

const int N= 1e3 + 10;
int dp[N][N][10];
int vis[2][N];
int a[N], b[N];
int mnTime[N][N], n;
//mnTime[i][j]: the minimum required amount of time for baudi to start at i, ends at j

int memo[N];
int solve(int i, int j, int spent){
         if(j > n){
                  return INT_MAX;
         }
         int &ret= dp[i][j][spent];
         if(ret != -1) return ret;

         //andi wants to read book i
         //baudi is reading book j and has spent [spent] hours reading it
         if(j == n)
         {
                  int sum = 0;
                  for(int k = i; k < n; k++)
                           sum += a[i];
                  return ret= sum;
         }

         ret= INT_MAX;
         if(i == j)
         {
                  if (spent == b[j]){
                           ret= solve(i, j + 1, 0);
                           if(j + 1 != n - 1) ret= min(ret, solve(i, j + 2, 0));
                           return ret;
                  }
                  return ret = solve(i, j, spent + 1) + 1;
         }

         if(a[i] <= b[j] - spent)
         {
                  //he will finish reading it before me
                  return ret= a[i] + solve(i + 1, j, spent + a[i]);
         }

         int L = j, R= n - 1, best= j;
         while(L <= R)
         {
                  int md= (L + R) / 2;
                  if(mnTime[j][md] - spent <= a[i])
                           best= md, L= md + 1;
                  else
                           R= md - 1;
         }



         for(int to = best - 50; to < best + 50; to++)
         {
                  if(to < j || to > n - 1)
                           continue;

                  if(mnTime[j][to] - spent <= a[i])
                  {
                           int rem= a[i] - mnTime[j][to] + spent;
                           int ch= solve(i + 1, to + 1, min(b[to + 1], rem));
                           if(to + 1 != n - 1) {
                                    //we can skip it
                                    ch= min(ch, solve(i + 1, to + 2, min(b[to + 2], rem)));
                           }
                           ret= min(ret, a[i] + ch);
                  }
         }
         return ret;
}
int32_t main(){
         cin.tie(0);
         cin.sync_with_stdio(0);

         cin>>n;
         for(int i = 0; i < n; i++){
                  cin>>a[i];
         }
         for(int i = 0; i < n; i++){
                  cin>>b[i];
         }
         for(int ed = n - 1; ed >= 0; ed--)
         {
                  memo[ed]= b[ed];
                  mnTime[ed][ed]= b[ed];
                  memo[ed + 1]= INT_MAX;
                  for(int i = ed - 1; i >= 0; i--){
                           memo[i]= b[i] + min(memo[i + 1], memo[i + 2]);
                           mnTime[i][ed]= memo[i];
                  }
         }
         memset(dp, -1, sizeof dp);
         cout<<solve(0, 0, 0)<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 84340kb

input:

6
3 1 1 1 1 2
1 5 3 3 7 4

output:

13

result:

ok single line: '13'

Test #2:

score: 0
Accepted
time: 0ms
memory: 83392kb

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 83976kb

input:

1
1
1

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 84232kb

input:

161
146 662 336 441 626 77 362 697 911 248 879 40 435 60 518 62 475 908 185 740 435 899 188 673 716 529 524 305 321 998 4 363 598 471 650 379 6 980 971 175 664 328 294 681 201 64 926 608 310 478 404 284 634 239 891 515 433 368 929 457 593 338 432 971 593 134 355 97 658 344 653 592 822 660 403 398 38...

output:

61599

result:

wrong answer 1st lines differ - expected: '80587', found: '61599'