oj.uz

Submission #1067969

# Submission time Handle Problem Language Result Execution time Memory
1067969 2024-08-21T06:15:20 Z hasan2006 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 87124 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 = 1e5 + 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;
            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, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3});
}*/
// 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: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: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 Correct 69 ms 83796 KB Output is correct
2 Correct 99 ms 85336 KB Output is correct
3 Correct 41 ms 80604 KB Output is correct
4 Correct 50 ms 80464 KB Output is correct
5 Execution timed out 1078 ms 87124 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 74320 KB Output is correct
2 Execution timed out 1030 ms 82000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80464 KB Output is correct
2 Correct 38 ms 80468 KB Output is correct
3 Incorrect 54 ms 81248 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21040785990629'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74372 KB Output is correct
2 Correct 27 ms 74332 KB Output is correct
3 Correct 41 ms 74228 KB Output is correct
4 Correct 31 ms 74240 KB Output is correct
5 Correct 30 ms 74388 KB Output is correct
6 Correct 28 ms 74332 KB Output is correct
7 Correct 45 ms 74324 KB Output is correct
8 Correct 35 ms 72272 KB Output is correct
9 Incorrect 29 ms 72284 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216535146944'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74372 KB Output is correct
2 Correct 27 ms 74332 KB Output is correct
3 Correct 41 ms 74228 KB Output is correct
4 Correct 31 ms 74240 KB Output is correct
5 Correct 30 ms 74388 KB Output is correct
6 Correct 28 ms 74332 KB Output is correct
7 Correct 45 ms 74324 KB Output is correct
8 Correct 35 ms 72272 KB Output is correct
9 Incorrect 29 ms 72284 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216535146944'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74372 KB Output is correct
2 Correct 27 ms 74332 KB Output is correct
3 Correct 41 ms 74228 KB Output is correct
4 Correct 31 ms 74240 KB Output is correct
5 Correct 30 ms 74388 KB Output is correct
6 Correct 28 ms 74332 KB Output is correct
7 Correct 45 ms 74324 KB Output is correct
8 Correct 35 ms 72272 KB Output is correct
9 Incorrect 29 ms 72284 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216535146944'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80464 KB Output is correct
2 Correct 38 ms 80468 KB Output is correct
3 Incorrect 54 ms 81248 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21040785990629'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 83796 KB Output is correct
2 Correct 99 ms 85336 KB Output is correct
3 Correct 41 ms 80604 KB Output is correct
4 Correct 50 ms 80464 KB Output is correct
5 Execution timed out 1078 ms 87124 KB Time limit exceeded
6 Halted 0 ms 0 KB -