oj.uz

Submission #1068651

# Submission time Handle Problem Language Result Execution time Memory
1068651 2024-08-21T11:09:25 Z hasan2006 Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 595028 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];
vector<ll>dp[N] , d[N];

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);
                dp[i][j] = max(dp[i][j] , max(dp[i - 1][x] , d[i - 1][x]));
            }
            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(6, 5, {5, 4, 0 , 2 , 1}, {0, 0, 0 , 0 , 0}, {979169285 ,288589606,  56346688 , 568303254 , 617066964});
}*/
// 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:41: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]
   41 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:42: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]
   42 |             while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp:52: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]
   52 |                 for(x = 0; x < v[i - 2].size(); x++){
      |                            ~~^~~~~~~~~~~~~~~~~
fish.cpp:53: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]
   53 |                     while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
      |                           ~~^~~~~~~~~~~~~~~~~
fish.cpp:58: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]
   58 |             for(x = l; x < v[i - 1].size(); x++){
      |                        ~~^~~~~~~~~~~~~~~~~
fish.cpp:59: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]
   59 |                 while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
      |                       ~~^~~~~~~~~~~~~
fish.cpp:27:40: warning: unused variable 'y' [-Wunused-variable]
   27 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                        ^
fish.cpp:27:44: warning: unused variable 'k' [-Wunused-variable]
   27 |     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 335 ms 595028 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 119 ms 289616 KB Output is correct
2 Execution timed out 1070 ms 297516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 347732 KB Output is correct
2 Correct 182 ms 347744 KB Output is correct
3 Correct 162 ms 315476 KB Output is correct
4 Correct 163 ms 329884 KB Output is correct
5 Correct 156 ms 298384 KB Output is correct
6 Correct 164 ms 298412 KB Output is correct
7 Correct 154 ms 298324 KB Output is correct
8 Correct 165 ms 298392 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289828 KB Output is correct
2 Correct 112 ms 289784 KB Output is correct
3 Correct 120 ms 289616 KB Output is correct
4 Correct 118 ms 289616 KB Output is correct
5 Correct 121 ms 289616 KB Output is correct
6 Correct 117 ms 289636 KB Output is correct
7 Correct 118 ms 289804 KB Output is correct
8 Correct 113 ms 289860 KB Output is correct
9 Correct 129 ms 289876 KB Output is correct
10 Correct 116 ms 289820 KB Output is correct
11 Correct 113 ms 289872 KB Output is correct
12 Incorrect 114 ms 289860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449924300888'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289828 KB Output is correct
2 Correct 112 ms 289784 KB Output is correct
3 Correct 120 ms 289616 KB Output is correct
4 Correct 118 ms 289616 KB Output is correct
5 Correct 121 ms 289616 KB Output is correct
6 Correct 117 ms 289636 KB Output is correct
7 Correct 118 ms 289804 KB Output is correct
8 Correct 113 ms 289860 KB Output is correct
9 Correct 129 ms 289876 KB Output is correct
10 Correct 116 ms 289820 KB Output is correct
11 Correct 113 ms 289872 KB Output is correct
12 Incorrect 114 ms 289860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449924300888'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 289828 KB Output is correct
2 Correct 112 ms 289784 KB Output is correct
3 Correct 120 ms 289616 KB Output is correct
4 Correct 118 ms 289616 KB Output is correct
5 Correct 121 ms 289616 KB Output is correct
6 Correct 117 ms 289636 KB Output is correct
7 Correct 118 ms 289804 KB Output is correct
8 Correct 113 ms 289860 KB Output is correct
9 Correct 129 ms 289876 KB Output is correct
10 Correct 116 ms 289820 KB Output is correct
11 Correct 113 ms 289872 KB Output is correct
12 Incorrect 114 ms 289860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449924300888'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 347732 KB Output is correct
2 Correct 182 ms 347744 KB Output is correct
3 Correct 162 ms 315476 KB Output is correct
4 Correct 163 ms 329884 KB Output is correct
5 Correct 156 ms 298384 KB Output is correct
6 Correct 164 ms 298412 KB Output is correct
7 Correct 154 ms 298324 KB Output is correct
8 Correct 165 ms 298392 KB Output is correct
9 Correct 211 ms 350032 KB Output is correct
10 Correct 162 ms 295248 KB Output is correct
11 Correct 202 ms 300624 KB Output is correct
12 Correct 113 ms 289832 KB Output is correct
13 Correct 116 ms 289780 KB Output is correct
14 Correct 113 ms 289804 KB Output is correct
15 Correct 118 ms 289620 KB Output is correct
16 Correct 122 ms 289800 KB Output is correct
17 Correct 118 ms 289616 KB Output is correct
18 Correct 167 ms 347548 KB Output is correct
19 Correct 165 ms 347728 KB Output is correct
20 Correct 164 ms 347532 KB Output is correct
21 Correct 155 ms 347988 KB Output is correct
22 Incorrect 209 ms 351056 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45556153296716'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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