oj.uz

Submission #1068696

# Submission time Handle Problem Language Result Execution time Memory
1068696 2024-08-21T11:24:17 Z hasan2006 Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 592208 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 = 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(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 = 0; 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 339 ms 592208 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 117 ms 288344 KB Output is correct
2 Execution timed out 1066 ms 296008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 346420 KB Output is correct
2 Correct 178 ms 346304 KB Output is correct
3 Correct 164 ms 314192 KB Output is correct
4 Correct 175 ms 328532 KB Output is correct
5 Correct 161 ms 297084 KB Output is correct
6 Correct 210 ms 297040 KB Output is correct
7 Correct 200 ms 297020 KB Output is correct
8 Correct 188 ms 297016 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 288340 KB Output is correct
2 Correct 137 ms 288472 KB Output is correct
3 Correct 138 ms 288308 KB Output is correct
4 Correct 179 ms 289620 KB Output is correct
5 Correct 129 ms 288472 KB Output is correct
6 Correct 138 ms 289668 KB Output is correct
7 Correct 141 ms 289616 KB Output is correct
8 Correct 143 ms 289860 KB Output is correct
9 Correct 158 ms 289824 KB Output is correct
10 Correct 163 ms 288468 KB Output is correct
11 Correct 117 ms 288340 KB Output is correct
12 Incorrect 131 ms 288596 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 123 ms 288340 KB Output is correct
2 Correct 137 ms 288472 KB Output is correct
3 Correct 138 ms 288308 KB Output is correct
4 Correct 179 ms 289620 KB Output is correct
5 Correct 129 ms 288472 KB Output is correct
6 Correct 138 ms 289668 KB Output is correct
7 Correct 141 ms 289616 KB Output is correct
8 Correct 143 ms 289860 KB Output is correct
9 Correct 158 ms 289824 KB Output is correct
10 Correct 163 ms 288468 KB Output is correct
11 Correct 117 ms 288340 KB Output is correct
12 Incorrect 131 ms 288596 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 123 ms 288340 KB Output is correct
2 Correct 137 ms 288472 KB Output is correct
3 Correct 138 ms 288308 KB Output is correct
4 Correct 179 ms 289620 KB Output is correct
5 Correct 129 ms 288472 KB Output is correct
6 Correct 138 ms 289668 KB Output is correct
7 Correct 141 ms 289616 KB Output is correct
8 Correct 143 ms 289860 KB Output is correct
9 Correct 158 ms 289824 KB Output is correct
10 Correct 163 ms 288468 KB Output is correct
11 Correct 117 ms 288340 KB Output is correct
12 Incorrect 131 ms 288596 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 171 ms 346420 KB Output is correct
2 Correct 178 ms 346304 KB Output is correct
3 Correct 164 ms 314192 KB Output is correct
4 Correct 175 ms 328532 KB Output is correct
5 Correct 161 ms 297084 KB Output is correct
6 Correct 210 ms 297040 KB Output is correct
7 Correct 200 ms 297020 KB Output is correct
8 Correct 188 ms 297016 KB Output is correct
9 Correct 203 ms 348564 KB Output is correct
10 Correct 224 ms 295412 KB Output is correct
11 Correct 209 ms 302412 KB Output is correct
12 Correct 142 ms 288340 KB Output is correct
13 Correct 133 ms 288340 KB Output is correct
14 Correct 156 ms 288496 KB Output is correct
15 Correct 121 ms 288340 KB Output is correct
16 Correct 143 ms 289620 KB Output is correct
17 Correct 136 ms 289620 KB Output is correct
18 Correct 173 ms 347732 KB Output is correct
19 Correct 201 ms 347732 KB Output is correct
20 Correct 217 ms 347752 KB Output is correct
21 Correct 205 ms 347732 KB Output is correct
22 Incorrect 253 ms 353140 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 339 ms 592208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -