oj.uz

Submission #922750

# Submission time Handle Problem Language Result Execution time Memory
922750 2024-02-06T05:33:22 Z vjudge1 Collecting Stamps 3 (JOI20_ho_t3) C++17
100 / 100
 222 ms 137308 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
#define y1 yy
#define ppb pop_back
#define gcd(a,b) __gcd(a,b)
#define in insert

const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};

const int inf=1e18;
const int N=1e6;
const int MAX=210;
const int mod=1e9+7;

int n,l;
int x[MAX];
int t[MAX];
int dp[MAX][MAX][MAX][2];

int dist(int x,int y){
  if(x>y)swap(x,y);
  return min(y-x,l+x-y);
}

void solve(){
  cin>>n>>l;
  for(int i=1;i<=n;i++)cin>>x[i];
  for(int i=1;i<=n;i++)cin>>t[i];
  x[n+1]=l;
  t[n+1]=inf;
  x[0]=l;
  t[0]=inf;
  n++;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      for(int k=0;k<=n;k++){
        dp[i][j][k][0]=dp[i][j][k][1]=inf;
      }
    }
  }
  dp[n][0][1][0]=dp[n][0][1][1]=0;
  for(int r=n;r>=1;r--){
    for(int l=0;l<r;l++){
      for(int cnt=1;cnt<=n;cnt++){
        for(int k=0;k<2;k++){
          int pos;
          if(k==1){
            pos=x[l];
          }
          else{
            pos=x[r];
          }
          {
            dp[r][l+1][cnt][1]=min(dp[r][l+1][cnt][1],dp[r][l][cnt][k]+dist(pos,x[l+1]));
          }
          {
            dp[r-1][l][cnt][0]=min(dp[r-1][l][cnt][0],dp[r][l][cnt][k]+dist(pos,x[r-1]));
          }
          if(dp[r][l][cnt][k]+dist(pos,x[l+1])<=t[l+1]){
            dp[r][l+1][cnt+1][1]=min(dp[r][l+1][cnt+1][1],dp[r][l][cnt][k]+dist(pos,x[l+1]));
          }
          if(dp[r][l][cnt][k]+dist(pos,x[r-1])<=t[r-1]){
            dp[r-1][l][cnt+1][0]=min(dp[r-1][l][cnt+1][0],dp[r][l][cnt][k]+dist(pos,x[r-1]));
          }
        }
      }
    }
  }
  for(int r=n;r>=1;r--){
    for(int l=0;l<=r;l++){
      for(int cnt=1;cnt<=n;cnt++){
        for(int k=0;k<2;k++){
          // cout<<r<<" "<<l<<" "<<cnt<<" "<<k<<" "<<dp[r][l][cnt][k]<<"\n";
        }
      }
    }
  }
  int ans=1;
  for(int i=1;i<n;i++){
    for(int cnt=1;cnt<=n;cnt++){
      for(int k=0;k<2;k++){
        if(dp[i+1][i][cnt][k]!=inf){
          ans=max(ans,cnt);
          // cout<<i<<" "<<k<<" "<<cnt<<"\n";
        }
      }
    }
  }
  cout<<ans-1<<"\n";
}

main(){
  // freopen("prizes.in", "r", stdin);
  // freopen("prizes.out", "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

ho_t3.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10660 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 1 ms 10588 KB Output is correct
25 Correct 2 ms 10712 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 1 ms 6608 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12636 KB Output is correct
31 Correct 1 ms 10588 KB Output is correct
32 Correct 2 ms 10588 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12752 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 150 ms 116976 KB Output is correct
19 Correct 72 ms 85336 KB Output is correct
20 Correct 34 ms 65628 KB Output is correct
21 Correct 72 ms 82780 KB Output is correct
22 Correct 96 ms 95876 KB Output is correct
23 Correct 30 ms 62556 KB Output is correct
24 Correct 19 ms 57944 KB Output is correct
25 Correct 29 ms 62300 KB Output is correct
26 Correct 9 ms 41640 KB Output is correct
27 Correct 31 ms 62808 KB Output is correct
28 Correct 18 ms 55900 KB Output is correct
29 Correct 30 ms 63324 KB Output is correct
30 Correct 21 ms 59992 KB Output is correct
31 Correct 28 ms 62300 KB Output is correct
32 Correct 12 ms 47760 KB Output is correct
33 Correct 25 ms 62300 KB Output is correct
34 Correct 9 ms 39640 KB Output is correct
35 Correct 24 ms 61788 KB Output is correct
36 Correct 11 ms 45660 KB Output is correct
37 Correct 25 ms 62812 KB Output is correct
38 Correct 14 ms 49756 KB Output is correct
39 Correct 27 ms 63580 KB Output is correct
40 Correct 15 ms 51860 KB Output is correct
41 Correct 195 ms 136264 KB Output is correct
42 Correct 118 ms 102952 KB Output is correct
43 Correct 199 ms 136276 KB Output is correct
44 Correct 105 ms 102148 KB Output is correct
45 Correct 199 ms 136272 KB Output is correct
46 Correct 110 ms 102740 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10660 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 1 ms 10588 KB Output is correct
25 Correct 2 ms 10712 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 1 ms 6608 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12636 KB Output is correct
31 Correct 1 ms 10588 KB Output is correct
32 Correct 2 ms 10588 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12752 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 150 ms 116976 KB Output is correct
37 Correct 72 ms 85336 KB Output is correct
38 Correct 34 ms 65628 KB Output is correct
39 Correct 72 ms 82780 KB Output is correct
40 Correct 96 ms 95876 KB Output is correct
41 Correct 30 ms 62556 KB Output is correct
42 Correct 19 ms 57944 KB Output is correct
43 Correct 29 ms 62300 KB Output is correct
44 Correct 9 ms 41640 KB Output is correct
45 Correct 31 ms 62808 KB Output is correct
46 Correct 18 ms 55900 KB Output is correct
47 Correct 30 ms 63324 KB Output is correct
48 Correct 21 ms 59992 KB Output is correct
49 Correct 28 ms 62300 KB Output is correct
50 Correct 12 ms 47760 KB Output is correct
51 Correct 25 ms 62300 KB Output is correct
52 Correct 9 ms 39640 KB Output is correct
53 Correct 24 ms 61788 KB Output is correct
54 Correct 11 ms 45660 KB Output is correct
55 Correct 25 ms 62812 KB Output is correct
56 Correct 14 ms 49756 KB Output is correct
57 Correct 27 ms 63580 KB Output is correct
58 Correct 15 ms 51860 KB Output is correct
59 Correct 195 ms 136264 KB Output is correct
60 Correct 118 ms 102952 KB Output is correct
61 Correct 199 ms 136276 KB Output is correct
62 Correct 105 ms 102148 KB Output is correct
63 Correct 199 ms 136272 KB Output is correct
64 Correct 110 ms 102740 KB Output is correct
65 Correct 169 ms 126156 KB Output is correct
66 Correct 150 ms 118320 KB Output is correct
67 Correct 139 ms 114888 KB Output is correct
68 Correct 122 ms 108624 KB Output is correct
69 Correct 170 ms 124960 KB Output is correct
70 Correct 196 ms 121172 KB Output is correct
71 Correct 150 ms 122192 KB Output is correct
72 Correct 204 ms 123224 KB Output is correct
73 Correct 136 ms 116680 KB Output is correct
74 Correct 176 ms 111192 KB Output is correct
75 Correct 154 ms 119380 KB Output is correct
76 Correct 209 ms 132144 KB Output is correct
77 Correct 178 ms 131924 KB Output is correct
78 Correct 144 ms 109616 KB Output is correct
79 Correct 128 ms 112228 KB Output is correct
80 Correct 214 ms 129872 KB Output is correct
81 Correct 134 ms 112892 KB Output is correct
82 Correct 146 ms 117620 KB Output is correct
83 Correct 198 ms 136272 KB Output is correct
84 Correct 150 ms 121168 KB Output is correct
85 Correct 173 ms 129108 KB Output is correct
86 Correct 168 ms 127132 KB Output is correct
87 Correct 147 ms 119376 KB Output is correct
88 Correct 222 ms 137300 KB Output is correct
89 Correct 197 ms 137304 KB Output is correct
90 Correct 152 ms 120404 KB Output is correct
91 Correct 207 ms 137296 KB Output is correct
92 Correct 194 ms 137308 KB Output is correct
93 Correct 208 ms 134996 KB Output is correct