oj.uz

Submission #1068838

# Submission time Handle Problem Language Result Execution time Memory
1068838 2024-08-21T12:27:37 Z hasan2006 Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 592212 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 = 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: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 Runtime error 343 ms 592212 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 129 ms 288336 KB Output is correct
2 Execution timed out 1083 ms 296016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 346312 KB Output is correct
2 Correct 188 ms 346240 KB Output is correct
3 Correct 185 ms 314192 KB Output is correct
4 Correct 233 ms 328708 KB Output is correct
5 Correct 201 ms 297040 KB Output is correct
6 Correct 190 ms 297040 KB Output is correct
7 Correct 158 ms 296936 KB Output is correct
8 Correct 167 ms 297020 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 288336 KB Output is correct
2 Correct 123 ms 288340 KB Output is correct
3 Correct 132 ms 288340 KB Output is correct
4 Correct 118 ms 288284 KB Output is correct
5 Correct 134 ms 288336 KB Output is correct
6 Correct 115 ms 288364 KB Output is correct
7 Correct 142 ms 288336 KB Output is correct
8 Correct 142 ms 288324 KB Output is correct
9 Correct 167 ms 288340 KB Output is correct
10 Correct 119 ms 288376 KB Output is correct
11 Correct 152 ms 288340 KB Output is correct
12 Correct 129 ms 288592 KB Output is correct
13 Correct 149 ms 288592 KB Output is correct
14 Correct 122 ms 288344 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 288336 KB Output is correct
2 Correct 123 ms 288340 KB Output is correct
3 Correct 132 ms 288340 KB Output is correct
4 Correct 118 ms 288284 KB Output is correct
5 Correct 134 ms 288336 KB Output is correct
6 Correct 115 ms 288364 KB Output is correct
7 Correct 142 ms 288336 KB Output is correct
8 Correct 142 ms 288324 KB Output is correct
9 Correct 167 ms 288340 KB Output is correct
10 Correct 119 ms 288376 KB Output is correct
11 Correct 152 ms 288340 KB Output is correct
12 Correct 129 ms 288592 KB Output is correct
13 Correct 149 ms 288592 KB Output is correct
14 Correct 122 ms 288344 KB Output is correct
15 Correct 148 ms 288592 KB Output is correct
16 Runtime error 356 ms 584784 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 134 ms 288336 KB Output is correct
2 Correct 123 ms 288340 KB Output is correct
3 Correct 132 ms 288340 KB Output is correct
4 Correct 118 ms 288284 KB Output is correct
5 Correct 134 ms 288336 KB Output is correct
6 Correct 115 ms 288364 KB Output is correct
7 Correct 142 ms 288336 KB Output is correct
8 Correct 142 ms 288324 KB Output is correct
9 Correct 167 ms 288340 KB Output is correct
10 Correct 119 ms 288376 KB Output is correct
11 Correct 152 ms 288340 KB Output is correct
12 Correct 129 ms 288592 KB Output is correct
13 Correct 149 ms 288592 KB Output is correct
14 Correct 122 ms 288344 KB Output is correct
15 Correct 148 ms 288592 KB Output is correct
16 Runtime error 356 ms 584784 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 213 ms 346312 KB Output is correct
2 Correct 188 ms 346240 KB Output is correct
3 Correct 185 ms 314192 KB Output is correct
4 Correct 233 ms 328708 KB Output is correct
5 Correct 201 ms 297040 KB Output is correct
6 Correct 190 ms 297040 KB Output is correct
7 Correct 158 ms 296936 KB Output is correct
8 Correct 167 ms 297020 KB Output is correct
9 Correct 263 ms 348776 KB Output is correct
10 Correct 220 ms 293920 KB Output is correct
11 Correct 195 ms 299440 KB Output is correct
12 Correct 158 ms 288296 KB Output is correct
13 Correct 128 ms 288488 KB Output is correct
14 Correct 152 ms 288364 KB Output is correct
15 Correct 146 ms 288340 KB Output is correct
16 Correct 113 ms 288336 KB Output is correct
17 Correct 209 ms 288344 KB Output is correct
18 Correct 174 ms 346336 KB Output is correct
19 Correct 181 ms 346256 KB Output is correct
20 Correct 169 ms 346392 KB Output is correct
21 Correct 179 ms 346196 KB Output is correct
22 Correct 230 ms 349688 KB Output is correct
23 Correct 245 ms 350808 KB Output is correct
24 Correct 245 ms 354132 KB Output is correct

Subtask #8
0 / 16.0

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