oj.uz

Submission #1068470

# Submission time Handle Problem Language Result Execution time Memory
1068470 2024-08-21T10:03:53 Z hasan2006 Catfish Farm (IOI22_fish) C++17
9 / 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];
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);
            }
            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 348 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 119 ms 288332 KB Output is correct
2 Execution timed out 1022 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 173 ms 346192 KB Output is correct
2 Correct 169 ms 346180 KB Output is correct
3 Correct 175 ms 314192 KB Output is correct
4 Correct 178 ms 328532 KB Output is correct
5 Correct 156 ms 297044 KB Output is correct
6 Correct 164 ms 296996 KB Output is correct
7 Correct 155 ms 297028 KB Output is correct
8 Correct 158 ms 297040 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 288336 KB Output is correct
2 Correct 113 ms 288404 KB Output is correct
3 Correct 143 ms 288340 KB Output is correct
4 Correct 128 ms 288392 KB Output is correct
5 Correct 126 ms 288336 KB Output is correct
6 Correct 112 ms 288336 KB Output is correct
7 Correct 118 ms 288336 KB Output is correct
8 Correct 134 ms 288340 KB Output is correct
9 Correct 127 ms 288340 KB Output is correct
10 Correct 117 ms 288596 KB Output is correct
11 Incorrect 120 ms 288324 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278452976884'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 288336 KB Output is correct
2 Correct 113 ms 288404 KB Output is correct
3 Correct 143 ms 288340 KB Output is correct
4 Correct 128 ms 288392 KB Output is correct
5 Correct 126 ms 288336 KB Output is correct
6 Correct 112 ms 288336 KB Output is correct
7 Correct 118 ms 288336 KB Output is correct
8 Correct 134 ms 288340 KB Output is correct
9 Correct 127 ms 288340 KB Output is correct
10 Correct 117 ms 288596 KB Output is correct
11 Incorrect 120 ms 288324 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278452976884'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 288336 KB Output is correct
2 Correct 113 ms 288404 KB Output is correct
3 Correct 143 ms 288340 KB Output is correct
4 Correct 128 ms 288392 KB Output is correct
5 Correct 126 ms 288336 KB Output is correct
6 Correct 112 ms 288336 KB Output is correct
7 Correct 118 ms 288336 KB Output is correct
8 Correct 134 ms 288340 KB Output is correct
9 Correct 127 ms 288340 KB Output is correct
10 Correct 117 ms 288596 KB Output is correct
11 Incorrect 120 ms 288324 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278452976884'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 346192 KB Output is correct
2 Correct 169 ms 346180 KB Output is correct
3 Correct 175 ms 314192 KB Output is correct
4 Correct 178 ms 328532 KB Output is correct
5 Correct 156 ms 297044 KB Output is correct
6 Correct 164 ms 296996 KB Output is correct
7 Correct 155 ms 297028 KB Output is correct
8 Correct 158 ms 297040 KB Output is correct
9 Correct 222 ms 348752 KB Output is correct
10 Correct 156 ms 293956 KB Output is correct
11 Correct 191 ms 299344 KB Output is correct
12 Correct 113 ms 288360 KB Output is correct
13 Correct 125 ms 288336 KB Output is correct
14 Correct 113 ms 288336 KB Output is correct
15 Correct 137 ms 288336 KB Output is correct
16 Correct 147 ms 288496 KB Output is correct
17 Correct 115 ms 288340 KB Output is correct
18 Correct 177 ms 346196 KB Output is correct
19 Correct 155 ms 346200 KB Output is correct
20 Correct 169 ms 346192 KB Output is correct
21 Correct 167 ms 346192 KB Output is correct
22 Incorrect 237 ms 349776 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45454347184491'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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