Submission #1068849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068849		hasan2006	Catfish Farm (IOI22_fish)	C++17	58 / 100	1086 ms	359436 KiB

fish

#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 + 5];
vector<ll>dp[N + 5] , d[N + 5];
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(l < v[i- 1].size() && v[i - 1][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(4, 4, {3, 0 , 2 , 1}, {0, 0, 1 , 3}, {1 , 4 , 1 , 2});
}*/
// Author : حسن

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:39: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]
   39 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:40: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]
   40 |             while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp:45:18: 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]
   45 |             if(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:26:40: warning: unused variable 'y' [-Wunused-variable]
   26 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                        ^
fish.cpp:26:44: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
      |                                            ^

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16