Submission #826192

#	Time	Username	Problem	Language	Result	Execution time	Memory
826192		lollipop	Catfish Farm (IOI22_fish)	C++17	47 / 100	68 ms	17984 KiB

fish

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;

#include "fish.h"

ll sum[ 305 ][ 305 ] ;
ll pos[ 305 ][ 305 ] ;
ll dp_bl[ 305 ][ 305 ] ;
ll dp_dk[ 305 ][ 305 ] ;
//vector < pair < int , int > > v[ 305 ] ;

ll ss[ 2 ][ N ] , ps[ 2 ][ N ] ;
ll get1( int N, int M, vector<int> X, vector<int> Y,vector<int> W ){
       FOR( i , M ){
        ps[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
    }
    FOR( i , N ){
        FOR( j , N ){
          if( j != 0 ) ss[ i ][ j ] = ss[ i ][ j - 1 ] ;
          ss[ i ][ j ] += ps[ i ][ j ] ;
        }
    }
    return 0 ;

}
ll sum2[ N ][ 4 ] ;
ll pos2[ N ][ 4 ] ;
ll dp_bl2[ N ][ 4 ] ;
ll dp_dk2[ N ][ 4 ] ;

ll get2( int N, int M, vector<int> X, vector<int> Y,vector<int> W ){
   
    FOR( i , M ){
        pos2[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
    }
    int m = min( N , 3 ) ;
    FOR( i , N ){
        FOR( j , m ){
          if( j != 0 ) sum2[ i ][ j ] = sum2[ i ][ j - 1 ] ;
          sum2[ i ][ j ] += pos2[ i ][ j ] ;
        }
    }

    // dp_bl
    // dp_dk
    FOR( i , N ){
      if( i == 0 ){
       FOR( j , m + 1 ){
         dp_bl2[ i ][ j ] = 0 ;
         dp_dk2[ i ][ j ] = 0 ;
       }
        continue ;
      }
      FOR( j , m + 1 ){
        // j ari sadamdec ginda kedeli 
        // cases
        // pirveli ginda ro winas kedeli amaze maxali iyos 
        for( int wn = j ; wn < m + 1 ; wn ++ ){
            ll cur ; 
            ll sm = 0 ; 
            if( wn != 0 ) sm = sum2[ i ][ wn - 1 ] ; 
            if( j != 0 ) sm = sm - sum2[ i ][ j - 1 ] ;

            cur = dp_bl2[ i - 1 ][ wn ] + sm ;
            dp_bl2[ i ][ j ] = max( dp_bl2[ i ][ j ] , cur ) ;
            dp_dk2[ i ][ wn ] = max( dp_dk2[ i ][ wn ] , cur ) ; 
        }
        for( int wn = 0 ; wn <= j ; wn ++ ){
           ll cur ;
           ll sm = sum2[ i - 1 ][ j - 1 ] ;
           if( wn != 0 ) sm = sm - sum2[ i - 1 ][ wn - 1 ] ;
           cur = sm + dp_dk2[ i - 1 ][ wn ] ;
           dp_bl2[ i ][ j ] = max( dp_bl2[ i ][ j ] , cur ) ;
           dp_dk2[ i ][ j ] = max( dp_dk2[ i ][ j ] , cur ) ;
        }
      }
    }
    ll ans = 0 ;
    FOR( j , m + 1 ){
        ans = max( ans , dp_bl2[ N - 1 ][ j ] ) ;
        ans = max( ans , dp_dk2[ N - 1 ][ j ] ) ; 
    }
    return ans ;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
    int tt = 0 ;
    ll sm = 0 , mm = 0 , mm1 = 0 ; 
    FOR( i , M ){
      sm = sm + W[ i ] ;
      if( X[ i ] % 2 == 1 ) tt =-1 ;
      mm = max( mm , X[ i ]*( 1LL) ) ;
      mm1 = max( mm1 , Y[ i ]*( 1LL ) ) ;
    }
    if( tt == 0 ) return sm ;

    // if( mm <= 1 ){
    //     return get1( N , M , X , Y , W ) ;
    // }
    if( mm1 == 0 ){
        return get2( N , M , X , Y , W ) ;
    }

    FOR( i , M ){
        pos[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
    }
    FOR( i , N ){
        FOR( j , N ){
          if( j != 0 ) sum[ i ][ j ] = sum[ i ][ j - 1 ] ;
          sum[ i ][ j ] += pos[ i ][ j ] ;
        }
    }

    // dp_bl
    // dp_dk

    FOR( i , N ){
      if( i == 0 ){
       FOR( j , N + 1 ){
         dp_bl[ i ][ j ] = 0 ;
         dp_dk[ i ][ j ] = 0 ;
       }
        continue ;
      }
      FOR( j , N + 1 ){
        // j ari sadamdec ginda kedeli 
        // cases
        // pirveli ginda ro winas kedeli amaze maxali iyos 
        for( int wn = j ; wn < N + 1 ; wn ++ ){
            ll cur ; 
            ll sm = 0 ; 
            if( wn != 0 ) sm = sum[ i ][ wn - 1 ] ; 
            if( j != 0 ) sm = sm - sum[ i ][ j - 1 ] ;

            cur = dp_bl[ i - 1 ][ wn ] + sm ;
            dp_bl[ i ][ j ] = max( dp_bl[ i ][ j ] , cur ) ;
            dp_dk[ i ][ wn ] = max( dp_dk[ i ][ wn ] , cur ) ; 
        }
        for( int wn = 0 ; wn <= j ; wn ++ ){
           ll cur ;
           ll sm = sum[ i - 1 ][ j - 1 ] ;
           if( wn != 0 ) sm = sm - sum[ i - 1 ][ wn - 1 ] ;
           cur = sm + dp_dk[ i - 1 ][ wn ] ;
           dp_bl[ i ][ j ] = max( dp_bl[ i ][ j ] , cur ) ;
           dp_dk[ i ][ j ] = max( dp_dk[ i ][ j ] , cur ) ;
        }
      }
    }
    ll ans = 0 ;
    FOR( j , N + 1 ){
        ans = max( ans , dp_bl[ N - 1 ][ j ] ) ;
        ans = max( ans , dp_dk[ N - 1 ][ j ] ) ; 
    }
    return ans ;
}

// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));

//   std::vector<int> X(M), Y(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//   }

//   long long result = max_weights(N, M, X, Y, W);
//   printf("%lld\n", result);
//   return 0;
// }

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