oj.uz

Submission #1068849

# Submission time Handle Problem Language Result Execution time Memory
1068849 2024-08-21T12:36:21 Z hasan2006 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 359436 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 4e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , c[N];
deque<pair<int,int>>v[N + 5];
vector<ll>dp[N + 5] , d[N + 5];
ll max_weights(int n, int m , vector<int>a , vector<int>b , vector<int>c){
    ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
    for(i = 0; i < m; i++)
        v[a[i]].pb({b[i], c[i]});
    for(i = 0; i < n; i++){
        sort(all(v[i]));
        if(v[i].size() == 0 || v[i].front().fi != 0)
            v[i].push_front({0 , 0});
        v[i].pb({n , 0});
        d[i].resize(v[i].size() , 0);
        dp[i].resize(v[i].size() , 0);
        if(i == 0)
        continue;
        l = 0 , s= 0;
        for(j = 0; j < v[i].size(); j++){
            while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
                s += v[i - 1][l].se , l++;
            f = 0;
            for(x = 0; x < l; x++)
                dp[i][j] = max(dp[i][j] , dp[i - 1][x] + s - f) , f += v[i - 1][x].se;
            if(l < v[i- 1].size() && v[i - 1][l].fi == v[i][j].fi)
                dp[i][j] = max(dp[i][j] , max(dp[i - 1][l] , d[i - 1][l]));
            r = l;
            f = 0;
            if(i > 1)
                for(x = 0; x < v[i - 2].size(); x++){
                    while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
                        f += v[i - 1][r].se , r++;
                    dp[i][j] = max(dp[i][j] , s + f + max(dp[i - 2][x] , d[i - 2][x]));
                }
            f = 0 , r = j;
            for(x = l; x < v[i - 1].size(); x++){
                while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
                    f += v[i][r].se , r++;
                d[i][j] = max(d[i][j] , max(dp[i - 1][x] , d[i - 1][x]) + f);
            }
            ans = max({ans , dp[i][j] , d[i][j]});
        }
    }
    return ans;
}
/*
int main(){
    TL;

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    cout<<max_weights(4, 4, {3, 0 , 2 , 1}, {0, 0, 1 , 3}, {1 , 4 , 1 , 2});
}*/
// Author : حسن

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:40:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if(l < v[i- 1].size() && v[i - 1][l].fi == v[i][j].fi)
      |                ~~^~~~~~~~~~~~~~~~
fish.cpp:50:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 for(x = 0; x < v[i - 2].size(); x++){
      |                            ~~^~~~~~~~~~~~~~~~~
fish.cpp:51:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                     while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
      |                           ~~^~~~~~~~~~~~~~~~~
fish.cpp:56:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(x = l; x < v[i - 1].size(); x++){
      |                        ~~^~~~~~~~~~~~~~~~~
fish.cpp:57:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
      |                       ~~^~~~~~~~~~~~~
fish.cpp:26:40: warning: unused variable 'y' [-Wunused-variable]
   26 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                        ^
fish.cpp:26:44: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                            ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 345684 KB Output is correct
2 Correct 245 ms 352848 KB Output is correct
3 Correct 185 ms 346176 KB Output is correct
4 Correct 187 ms 346180 KB Output is correct
5 Execution timed out 1045 ms 324012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 288344 KB Output is correct
2 Execution timed out 1043 ms 298944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 346196 KB Output is correct
2 Correct 181 ms 346196 KB Output is correct
3 Correct 176 ms 315220 KB Output is correct
4 Correct 208 ms 330520 KB Output is correct
5 Correct 147 ms 299860 KB Output is correct
6 Correct 155 ms 299348 KB Output is correct
7 Correct 156 ms 299856 KB Output is correct
8 Correct 153 ms 299996 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289708 KB Output is correct
2 Correct 112 ms 289876 KB Output is correct
3 Correct 181 ms 289620 KB Output is correct
4 Correct 112 ms 289620 KB Output is correct
5 Correct 112 ms 289620 KB Output is correct
6 Correct 112 ms 289616 KB Output is correct
7 Correct 110 ms 289616 KB Output is correct
8 Correct 115 ms 289616 KB Output is correct
9 Correct 106 ms 289872 KB Output is correct
10 Correct 115 ms 289880 KB Output is correct
11 Correct 111 ms 289760 KB Output is correct
12 Correct 109 ms 289772 KB Output is correct
13 Correct 106 ms 289772 KB Output is correct
14 Correct 117 ms 289872 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289708 KB Output is correct
2 Correct 112 ms 289876 KB Output is correct
3 Correct 181 ms 289620 KB Output is correct
4 Correct 112 ms 289620 KB Output is correct
5 Correct 112 ms 289620 KB Output is correct
6 Correct 112 ms 289616 KB Output is correct
7 Correct 110 ms 289616 KB Output is correct
8 Correct 115 ms 289616 KB Output is correct
9 Correct 106 ms 289872 KB Output is correct
10 Correct 115 ms 289880 KB Output is correct
11 Correct 111 ms 289760 KB Output is correct
12 Correct 109 ms 289772 KB Output is correct
13 Correct 106 ms 289772 KB Output is correct
14 Correct 117 ms 289872 KB Output is correct
15 Correct 125 ms 289864 KB Output is correct
16 Correct 151 ms 289876 KB Output is correct
17 Correct 247 ms 292692 KB Output is correct
18 Correct 269 ms 292792 KB Output is correct
19 Correct 208 ms 292728 KB Output is correct
20 Correct 198 ms 292644 KB Output is correct
21 Correct 235 ms 292532 KB Output is correct
22 Correct 403 ms 295508 KB Output is correct
23 Correct 125 ms 290388 KB Output is correct
24 Correct 158 ms 291668 KB Output is correct
25 Correct 121 ms 289816 KB Output is correct
26 Correct 141 ms 290388 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289708 KB Output is correct
2 Correct 112 ms 289876 KB Output is correct
3 Correct 181 ms 289620 KB Output is correct
4 Correct 112 ms 289620 KB Output is correct
5 Correct 112 ms 289620 KB Output is correct
6 Correct 112 ms 289616 KB Output is correct
7 Correct 110 ms 289616 KB Output is correct
8 Correct 115 ms 289616 KB Output is correct
9 Correct 106 ms 289872 KB Output is correct
10 Correct 115 ms 289880 KB Output is correct
11 Correct 111 ms 289760 KB Output is correct
12 Correct 109 ms 289772 KB Output is correct
13 Correct 106 ms 289772 KB Output is correct
14 Correct 117 ms 289872 KB Output is correct
15 Correct 125 ms 289864 KB Output is correct
16 Correct 151 ms 289876 KB Output is correct
17 Correct 247 ms 292692 KB Output is correct
18 Correct 269 ms 292792 KB Output is correct
19 Correct 208 ms 292728 KB Output is correct
20 Correct 198 ms 292644 KB Output is correct
21 Correct 235 ms 292532 KB Output is correct
22 Correct 403 ms 295508 KB Output is correct
23 Correct 125 ms 290388 KB Output is correct
24 Correct 158 ms 291668 KB Output is correct
25 Correct 121 ms 289816 KB Output is correct
26 Correct 141 ms 290388 KB Output is correct
27 Correct 114 ms 291652 KB Output is correct
28 Execution timed out 1086 ms 302672 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 346196 KB Output is correct
2 Correct 181 ms 346196 KB Output is correct
3 Correct 176 ms 315220 KB Output is correct
4 Correct 208 ms 330520 KB Output is correct
5 Correct 147 ms 299860 KB Output is correct
6 Correct 155 ms 299348 KB Output is correct
7 Correct 156 ms 299856 KB Output is correct
8 Correct 153 ms 299996 KB Output is correct
9 Correct 222 ms 351312 KB Output is correct
10 Correct 139 ms 297044 KB Output is correct
11 Correct 191 ms 304212 KB Output is correct
12 Correct 114 ms 289692 KB Output is correct
13 Correct 122 ms 289616 KB Output is correct
14 Correct 114 ms 289620 KB Output is correct
15 Correct 142 ms 289800 KB Output is correct
16 Correct 120 ms 289616 KB Output is correct
17 Correct 113 ms 289620 KB Output is correct
18 Correct 171 ms 347732 KB Output is correct
19 Correct 169 ms 347584 KB Output is correct
20 Correct 164 ms 347732 KB Output is correct
21 Correct 188 ms 347732 KB Output is correct
22 Correct 233 ms 353104 KB Output is correct
23 Correct 253 ms 355560 KB Output is correct
24 Correct 266 ms 359436 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 345684 KB Output is correct
2 Correct 245 ms 352848 KB Output is correct
3 Correct 185 ms 346176 KB Output is correct
4 Correct 187 ms 346180 KB Output is correct
5 Execution timed out 1045 ms 324012 KB Time limit exceeded
6 Halted 0 ms 0 KB -