oj.uz

Submission #1068026

# Submission time Handle Problem Language Result Execution time Memory
1068026 2024-08-21T06:46:14 Z hasan2006 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 593600 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].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(5, 4, {0, 1, 2, 3}, {0, 0, 0 , 0}, {1000000000, 1,1000000000,  1000000000});
}*/
// 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:28:40: warning: unused variable 'y' [-Wunused-variable]
   28 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                        ^
fish.cpp:28:44: warning: unused variable 'k' [-Wunused-variable]
   28 |     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 402 ms 593600 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 125 ms 288380 KB Output is correct
2 Execution timed out 1116 ms 298836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 294680 KB Output is correct
2 Correct 175 ms 294736 KB Output is correct
3 Incorrect 184 ms 296276 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21207416074342'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 288340 KB Output is correct
2 Correct 143 ms 288308 KB Output is correct
3 Correct 155 ms 288308 KB Output is correct
4 Correct 131 ms 288300 KB Output is correct
5 Correct 138 ms 288444 KB Output is correct
6 Correct 135 ms 288336 KB Output is correct
7 Correct 133 ms 288400 KB Output is correct
8 Correct 156 ms 288336 KB Output is correct
9 Correct 138 ms 288424 KB Output is correct
10 Correct 132 ms 288612 KB Output is correct
11 Incorrect 137 ms 288340 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 137 ms 288340 KB Output is correct
2 Correct 143 ms 288308 KB Output is correct
3 Correct 155 ms 288308 KB Output is correct
4 Correct 131 ms 288300 KB Output is correct
5 Correct 138 ms 288444 KB Output is correct
6 Correct 135 ms 288336 KB Output is correct
7 Correct 133 ms 288400 KB Output is correct
8 Correct 156 ms 288336 KB Output is correct
9 Correct 138 ms 288424 KB Output is correct
10 Correct 132 ms 288612 KB Output is correct
11 Incorrect 137 ms 288340 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 137 ms 288340 KB Output is correct
2 Correct 143 ms 288308 KB Output is correct
3 Correct 155 ms 288308 KB Output is correct
4 Correct 131 ms 288300 KB Output is correct
5 Correct 138 ms 288444 KB Output is correct
6 Correct 135 ms 288336 KB Output is correct
7 Correct 133 ms 288400 KB Output is correct
8 Correct 156 ms 288336 KB Output is correct
9 Correct 138 ms 288424 KB Output is correct
10 Correct 132 ms 288612 KB Output is correct
11 Incorrect 137 ms 288340 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 203 ms 294680 KB Output is correct
2 Correct 175 ms 294736 KB Output is correct
3 Incorrect 184 ms 296276 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21207416074342'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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