oj.uz

Submission #1056335

# Submission time Handle Problem Language Result Execution time Memory
1056335 2024-08-13T08:55:00 Z mychecksedad Catfish Farm (IOI22_fish) C++17
100 / 100
 274 ms 75348 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int> 
#define ff first
#define ss second
const int N = 100005;

// ll dp[N][N], pref[N][N], mx[N], dp2[N][N], suf[N][N];
vector<ll> dp2[N], dp[N], pref[N], suf[N], mxpref[N], mxpref2[N];
vector<pair<ll, ll>> a[N];
vector<ll> b[N];
ll mx[N];
int n;
ll get(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); //--x;
  return (x == -1 ? 0 : pref[pos][x]);
}
ll getmxpref2(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : mxpref2[pos][x]);
}
ll getmxpref(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : mxpref[pos][x]);
}
ll getsuf(int pos, ll idx){
  if(pos >= n) return 0;
  int x = lower_bound(all(b[pos]), idx) - b[pos].begin();
  return (x == b[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : dp2[pos][x]);
}
long long max_weights(int nn, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  n = nn;
  for(int i = 0; i < m; ++i){
    a[X[i]].pb({Y[i] + 1, W[i]});
    // a[X[i]][Y[i] + 1] = W[i];
    b[X[i]].pb(Y[i]);
  }
  for(int i = 0; i < n; ++i){
    a[i].pb({n + 1, 0});
    b[i].pb(n);
    sort(all(a[i]));
    sort(all(b[i]));
  }
  for(int i = 0; i < n; ++i){
    pref[i].resize(b[i].size() + 1);
    suf[i].resize(b[i].size() + 1);
    dp[i].resize(b[i].size() + 1);
    dp2[i].resize(b[i].size() + 1);
    mxpref[i].resize(b[i].size() + 1);
    mxpref2[i].resize(b[i].size() + 1);
    pref[i][0] = 0;
    for(int j = 1; j < b[i].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
  }
// cout << get(0, 20) << "F\n";
// for(int i = 0; i < 4; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << pref[i][j] << ' ';
// en;
// }
// en;en;
// for(int i = 0; i < 4; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << b[i][j] << ' ';
// en;
// }
// en;en;
  // return 0;
  mx[0] = 0;
  for(int i = 0; i < b[0].size(); ++i){
    dp[0][i] = dp2[0][i] = get(1, b[0][i]);
    mx[0] = max(mx[0], dp[0][i]);
  }
  suf[0][b[0].size()] = 0;
  for(int j = b[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
   
  // return 0ll;

  int i = 0;
  mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
  mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);

  for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
  for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));

  for(i = 1; i < n; ++i){
    mx[i] = 0;
    ll mx_pref = 0, mx_pref2 = 0;
    for(int j = 0; j < b[i].size(); ++j){
      ll pos = b[i][j];
      ll A = get(i - 1, pos);
      ll B = get(i, pos);
      ll C = get(i + 1, pos);
      ll add = A + C; //pref[i + 1][j] +  pref[i - 1][j];
      dp[i][j] = add;
      if(i > 2) dp[i][j] = max(dp[i][j], mx[i - 3] + add);
      dp2[i][j] = dp[i][j];

      // cout << i << ' ' << j << ' ' << add1 << ' ' <<add2 << ' ';
      ll x = add - B - A; //add - pref[i - 1][j] - pref[i][j];
      // for(int j2 = j + 1; j2 <= n; ++j2){
      //   dp[i][j] = max(dp[i][j], dp[i - 1][j2] + x);
      // }
      mx_pref2 = max(mx_pref2, getmxpref2(i - 1, pos));//max(mx_pref2, getdp2(i - 1, pos) - A - B); //dp2[i - 1][j] - pref[i - 1][j] - pref[i][j]);
      dp[i][j] = max(dp[i][j], mx_pref2 + add);
      dp2[i][j] = max(dp2[i][j], mx_pref2 + add);
      dp[i][j] = max(dp[i][j], getsuf(i - 1, pos) + x);//suf[i - 1][j] + x);
      if(i > 1){
        mx_pref = max(mx_pref, getmxpref(i - 2, pos));//dp[i - 2][j] - pref[i - 1][j]);
        dp[i][j] = max(dp[i][j], mx_pref + add);
        dp[i][j] = max(dp[i][j], getsuf(i - 2, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
        dp2[i][j] = max(dp2[i][j], mx_pref + add);
        dp2[i][j] = max(dp2[i][j], getsuf(i - 2, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
      }
      
      // cout << dp[i][j] << ' ' << dp2[i][j] << ' '  << i << ' ' << pos << ' ' <<A << ' ' << B << ' ' << C << endl; 
      mx[i] = max(mx[i], dp[i][j]);
    }
    suf[i][b[i].size()] = 0;

    for(int j = int(b[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);

    mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
    mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);

    for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
    for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
    // for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
    // en;
  }
// for(int i = 0; i < n; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << dp[i][j] << ' ';
//   en;
// }
  ll ans = mx[n - 1];

  return ans;
}

Compilation message

fish.cpp: In function 'long long int getsuf(int, long long int)':
fish.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   return (x == b[pos].size() ? 0 : suf[pos][x]);
      |           ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j = 1; j < b[i].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
      |                    ~~^~~~~~~~~~~~~
fish.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i < b[0].size(); ++i){
      |                  ~~^~~~~~~~~~~~~
fish.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
      |                  ~~^~~~~~~~~~~~~
fish.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
      |                  ~~^~~~~~~~~~~~~
fish.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int j = 0; j < b[i].size(); ++j){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
      |                    ~~^~~~~~~~~~~~~
fish.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
      |                    ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 49864 KB Output is correct
2 Correct 71 ms 54212 KB Output is correct
3 Correct 36 ms 44880 KB Output is correct
4 Correct 59 ms 44820 KB Output is correct
5 Correct 150 ms 73508 KB Output is correct
6 Correct 244 ms 74708 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 124 ms 57648 KB Output is correct
3 Correct 123 ms 63672 KB Output is correct
4 Correct 63 ms 49904 KB Output is correct
5 Correct 72 ms 54212 KB Output is correct
6 Correct 5 ms 19036 KB Output is correct
7 Correct 4 ms 19804 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 55 ms 44892 KB Output is correct
11 Correct 43 ms 44992 KB Output is correct
12 Correct 69 ms 50116 KB Output is correct
13 Correct 86 ms 54252 KB Output is correct
14 Correct 71 ms 50092 KB Output is correct
15 Correct 106 ms 53696 KB Output is correct
16 Correct 66 ms 50364 KB Output is correct
17 Correct 79 ms 53552 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 44892 KB Output is correct
2 Correct 41 ms 44892 KB Output is correct
3 Correct 68 ms 44624 KB Output is correct
4 Correct 56 ms 46428 KB Output is correct
5 Correct 126 ms 48772 KB Output is correct
6 Correct 102 ms 48928 KB Output is correct
7 Correct 150 ms 48724 KB Output is correct
8 Correct 100 ms 48908 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 3 ms 19836 KB Output is correct
5 Correct 5 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 4 ms 19804 KB Output is correct
8 Correct 3 ms 19800 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 6 ms 20068 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 3 ms 19804 KB Output is correct
13 Correct 3 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 3 ms 19836 KB Output is correct
5 Correct 5 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 4 ms 19804 KB Output is correct
8 Correct 3 ms 19800 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 6 ms 20068 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 3 ms 19804 KB Output is correct
13 Correct 3 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct
15 Correct 3 ms 19804 KB Output is correct
16 Correct 4 ms 20072 KB Output is correct
17 Correct 28 ms 24140 KB Output is correct
18 Correct 26 ms 24920 KB Output is correct
19 Correct 19 ms 24916 KB Output is correct
20 Correct 21 ms 24920 KB Output is correct
21 Correct 17 ms 24924 KB Output is correct
22 Correct 36 ms 29884 KB Output is correct
23 Correct 10 ms 20828 KB Output is correct
24 Correct 18 ms 22956 KB Output is correct
25 Correct 5 ms 19804 KB Output is correct
26 Correct 9 ms 20768 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 3 ms 19836 KB Output is correct
5 Correct 5 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 4 ms 19804 KB Output is correct
8 Correct 3 ms 19800 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 6 ms 20068 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 3 ms 19804 KB Output is correct
13 Correct 3 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct
15 Correct 3 ms 19804 KB Output is correct
16 Correct 4 ms 20072 KB Output is correct
17 Correct 28 ms 24140 KB Output is correct
18 Correct 26 ms 24920 KB Output is correct
19 Correct 19 ms 24916 KB Output is correct
20 Correct 21 ms 24920 KB Output is correct
21 Correct 17 ms 24924 KB Output is correct
22 Correct 36 ms 29884 KB Output is correct
23 Correct 10 ms 20828 KB Output is correct
24 Correct 18 ms 22956 KB Output is correct
25 Correct 5 ms 19804 KB Output is correct
26 Correct 9 ms 20768 KB Output is correct
27 Correct 5 ms 20572 KB Output is correct
28 Correct 165 ms 43112 KB Output is correct
29 Correct 174 ms 51260 KB Output is correct
30 Correct 151 ms 50772 KB Output is correct
31 Correct 178 ms 50756 KB Output is correct
32 Correct 161 ms 53128 KB Output is correct
33 Correct 152 ms 50740 KB Output is correct
34 Correct 176 ms 50752 KB Output is correct
35 Correct 58 ms 32804 KB Output is correct
36 Correct 172 ms 52804 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 44892 KB Output is correct
2 Correct 41 ms 44892 KB Output is correct
3 Correct 68 ms 44624 KB Output is correct
4 Correct 56 ms 46428 KB Output is correct
5 Correct 126 ms 48772 KB Output is correct
6 Correct 102 ms 48928 KB Output is correct
7 Correct 150 ms 48724 KB Output is correct
8 Correct 100 ms 48908 KB Output is correct
9 Correct 97 ms 48916 KB Output is correct
10 Correct 67 ms 42988 KB Output is correct
11 Correct 141 ms 66224 KB Output is correct
12 Correct 3 ms 19804 KB Output is correct
13 Correct 4 ms 19804 KB Output is correct
14 Correct 4 ms 19804 KB Output is correct
15 Correct 3 ms 19808 KB Output is correct
16 Correct 3 ms 19804 KB Output is correct
17 Correct 3 ms 19804 KB Output is correct
18 Correct 56 ms 44888 KB Output is correct
19 Correct 33 ms 44952 KB Output is correct
20 Correct 39 ms 44900 KB Output is correct
21 Correct 45 ms 44792 KB Output is correct
22 Correct 102 ms 53080 KB Output is correct
23 Correct 136 ms 66232 KB Output is correct
24 Correct 129 ms 66132 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 49864 KB Output is correct
2 Correct 71 ms 54212 KB Output is correct
3 Correct 36 ms 44880 KB Output is correct
4 Correct 59 ms 44820 KB Output is correct
5 Correct 150 ms 73508 KB Output is correct
6 Correct 244 ms 74708 KB Output is correct
7 Correct 6 ms 19036 KB Output is correct
8 Correct 124 ms 57648 KB Output is correct
9 Correct 123 ms 63672 KB Output is correct
10 Correct 63 ms 49904 KB Output is correct
11 Correct 72 ms 54212 KB Output is correct
12 Correct 5 ms 19036 KB Output is correct
13 Correct 4 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct
15 Correct 5 ms 19804 KB Output is correct
16 Correct 55 ms 44892 KB Output is correct
17 Correct 43 ms 44992 KB Output is correct
18 Correct 69 ms 50116 KB Output is correct
19 Correct 86 ms 54252 KB Output is correct
20 Correct 71 ms 50092 KB Output is correct
21 Correct 106 ms 53696 KB Output is correct
22 Correct 66 ms 50364 KB Output is correct
23 Correct 79 ms 53552 KB Output is correct
24 Correct 36 ms 44892 KB Output is correct
25 Correct 41 ms 44892 KB Output is correct
26 Correct 68 ms 44624 KB Output is correct
27 Correct 56 ms 46428 KB Output is correct
28 Correct 126 ms 48772 KB Output is correct
29 Correct 102 ms 48928 KB Output is correct
30 Correct 150 ms 48724 KB Output is correct
31 Correct 100 ms 48908 KB Output is correct
32 Correct 3 ms 19804 KB Output is correct
33 Correct 5 ms 19804 KB Output is correct
34 Correct 4 ms 19804 KB Output is correct
35 Correct 3 ms 19836 KB Output is correct
36 Correct 5 ms 19804 KB Output is correct
37 Correct 3 ms 19804 KB Output is correct
38 Correct 4 ms 19804 KB Output is correct
39 Correct 3 ms 19800 KB Output is correct
40 Correct 5 ms 19804 KB Output is correct
41 Correct 6 ms 20068 KB Output is correct
42 Correct 4 ms 19804 KB Output is correct
43 Correct 3 ms 19804 KB Output is correct
44 Correct 3 ms 19804 KB Output is correct
45 Correct 3 ms 19804 KB Output is correct
46 Correct 3 ms 19804 KB Output is correct
47 Correct 4 ms 20072 KB Output is correct
48 Correct 28 ms 24140 KB Output is correct
49 Correct 26 ms 24920 KB Output is correct
50 Correct 19 ms 24916 KB Output is correct
51 Correct 21 ms 24920 KB Output is correct
52 Correct 17 ms 24924 KB Output is correct
53 Correct 36 ms 29884 KB Output is correct
54 Correct 10 ms 20828 KB Output is correct
55 Correct 18 ms 22956 KB Output is correct
56 Correct 5 ms 19804 KB Output is correct
57 Correct 9 ms 20768 KB Output is correct
58 Correct 5 ms 20572 KB Output is correct
59 Correct 165 ms 43112 KB Output is correct
60 Correct 174 ms 51260 KB Output is correct
61 Correct 151 ms 50772 KB Output is correct
62 Correct 178 ms 50756 KB Output is correct
63 Correct 161 ms 53128 KB Output is correct
64 Correct 152 ms 50740 KB Output is correct
65 Correct 176 ms 50752 KB Output is correct
66 Correct 58 ms 32804 KB Output is correct
67 Correct 172 ms 52804 KB Output is correct
68 Correct 97 ms 48916 KB Output is correct
69 Correct 67 ms 42988 KB Output is correct
70 Correct 141 ms 66224 KB Output is correct
71 Correct 3 ms 19804 KB Output is correct
72 Correct 4 ms 19804 KB Output is correct
73 Correct 4 ms 19804 KB Output is correct
74 Correct 3 ms 19808 KB Output is correct
75 Correct 3 ms 19804 KB Output is correct
76 Correct 3 ms 19804 KB Output is correct
77 Correct 56 ms 44888 KB Output is correct
78 Correct 33 ms 44952 KB Output is correct
79 Correct 39 ms 44900 KB Output is correct
80 Correct 45 ms 44792 KB Output is correct
81 Correct 102 ms 53080 KB Output is correct
82 Correct 136 ms 66232 KB Output is correct
83 Correct 129 ms 66132 KB Output is correct
84 Correct 227 ms 71672 KB Output is correct
85 Correct 223 ms 73820 KB Output is correct
86 Correct 220 ms 70180 KB Output is correct
87 Correct 274 ms 72808 KB Output is correct
88 Correct 4 ms 19820 KB Output is correct
89 Correct 218 ms 72824 KB Output is correct
90 Correct 185 ms 74576 KB Output is correct
91 Correct 182 ms 75348 KB Output is correct