oj.uz

Submission #1068829

# Submission time Handle Problem Language Result Execution time Memory
1068829 2024-08-21T12:25:31 Z hasan2006 Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 593616 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(v[i][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 = 0; 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);
                dp[i][j] = max(dp[i][j] , max(dp[i - 1][x] , d[i - 1][x]));
            }
            d[i][j] = max(d[i][j] , dp[i][j]);
            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:40: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]
   40 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:41: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]
   41 |             while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp:51: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]
   51 |                 for(x = 0; x < v[i - 2].size(); x++){
      |                            ~~^~~~~~~~~~~~~~~~~
fish.cpp:52: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]
   52 |                     while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
      |                           ~~^~~~~~~~~~~~~~~~~
fish.cpp:57: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]
   57 |             for(x = 0; x < v[i - 1].size(); x++){
      |                        ~~^~~~~~~~~~~~~~~~~
fish.cpp:58: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]
   58 |                 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 Runtime error 351 ms 593616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 288336 KB Output is correct
2 Execution timed out 1112 ms 299172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 346196 KB Output is correct
2 Correct 161 ms 346388 KB Output is correct
3 Correct 216 ms 315216 KB Output is correct
4 Correct 175 ms 329304 KB Output is correct
5 Correct 183 ms 298576 KB Output is correct
6 Correct 177 ms 298064 KB Output is correct
7 Correct 169 ms 298580 KB Output is correct
8 Correct 189 ms 298612 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 288500 KB Output is correct
2 Correct 135 ms 288496 KB Output is correct
3 Correct 179 ms 288444 KB Output is correct
4 Correct 135 ms 288496 KB Output is correct
5 Correct 167 ms 288336 KB Output is correct
6 Correct 128 ms 288480 KB Output is correct
7 Correct 131 ms 288340 KB Output is correct
8 Correct 152 ms 288336 KB Output is correct
9 Correct 184 ms 288324 KB Output is correct
10 Correct 155 ms 288544 KB Output is correct
11 Correct 138 ms 288340 KB Output is correct
12 Correct 129 ms 288600 KB Output is correct
13 Correct 129 ms 288484 KB Output is correct
14 Correct 157 ms 288340 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 288500 KB Output is correct
2 Correct 135 ms 288496 KB Output is correct
3 Correct 179 ms 288444 KB Output is correct
4 Correct 135 ms 288496 KB Output is correct
5 Correct 167 ms 288336 KB Output is correct
6 Correct 128 ms 288480 KB Output is correct
7 Correct 131 ms 288340 KB Output is correct
8 Correct 152 ms 288336 KB Output is correct
9 Correct 184 ms 288324 KB Output is correct
10 Correct 155 ms 288544 KB Output is correct
11 Correct 138 ms 288340 KB Output is correct
12 Correct 129 ms 288600 KB Output is correct
13 Correct 129 ms 288484 KB Output is correct
14 Correct 157 ms 288340 KB Output is correct
15 Correct 147 ms 288488 KB Output is correct
16 Runtime error 363 ms 584628 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 288500 KB Output is correct
2 Correct 135 ms 288496 KB Output is correct
3 Correct 179 ms 288444 KB Output is correct
4 Correct 135 ms 288496 KB Output is correct
5 Correct 167 ms 288336 KB Output is correct
6 Correct 128 ms 288480 KB Output is correct
7 Correct 131 ms 288340 KB Output is correct
8 Correct 152 ms 288336 KB Output is correct
9 Correct 184 ms 288324 KB Output is correct
10 Correct 155 ms 288544 KB Output is correct
11 Correct 138 ms 288340 KB Output is correct
12 Correct 129 ms 288600 KB Output is correct
13 Correct 129 ms 288484 KB Output is correct
14 Correct 157 ms 288340 KB Output is correct
15 Correct 147 ms 288488 KB Output is correct
16 Runtime error 363 ms 584628 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 346196 KB Output is correct
2 Correct 161 ms 346388 KB Output is correct
3 Correct 216 ms 315216 KB Output is correct
4 Correct 175 ms 329304 KB Output is correct
5 Correct 183 ms 298576 KB Output is correct
6 Correct 177 ms 298064 KB Output is correct
7 Correct 169 ms 298580 KB Output is correct
8 Correct 189 ms 298612 KB Output is correct
9 Correct 233 ms 350060 KB Output is correct
10 Correct 187 ms 295616 KB Output is correct
11 Correct 220 ms 302928 KB Output is correct
12 Correct 146 ms 288340 KB Output is correct
13 Correct 138 ms 288412 KB Output is correct
14 Correct 130 ms 288324 KB Output is correct
15 Correct 134 ms 288468 KB Output is correct
16 Correct 144 ms 288336 KB Output is correct
17 Correct 135 ms 288444 KB Output is correct
18 Correct 217 ms 346336 KB Output is correct
19 Correct 191 ms 346192 KB Output is correct
20 Correct 222 ms 346208 KB Output is correct
21 Correct 210 ms 346344 KB Output is correct
22 Correct 311 ms 351828 KB Output is correct
23 Correct 327 ms 354248 KB Output is correct
24 Correct 324 ms 358216 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 351 ms 593616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -