oj.uz

Submission #826192

# Submission time Handle Problem Language Result Execution time Memory
826192 2023-08-15T11:03:18 Z lollipop Catfish Farm (IOI22_fish) C++17
47 / 100
 68 ms 17984 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2132 KB Output is correct
2 Correct 22 ms 2636 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 67 ms 7272 KB Output is correct
6 Correct 68 ms 7272 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 46 ms 11052 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 9 ms 9684 KB Output is correct
3 Correct 26 ms 13616 KB Output is correct
4 Correct 20 ms 13420 KB Output is correct
5 Correct 32 ms 17984 KB Output is correct
6 Correct 30 ms 17332 KB Output is correct
7 Correct 35 ms 17856 KB Output is correct
8 Correct 33 ms 17840 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 43 ms 3200 KB Output is correct
11 Correct 7 ms 1716 KB Output is correct
12 Correct 43 ms 3104 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 42 ms 3060 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 43 ms 3200 KB Output is correct
11 Correct 7 ms 1716 KB Output is correct
12 Correct 43 ms 3104 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 42 ms 3060 KB Output is correct
15 Correct 42 ms 3180 KB Output is correct
16 Correct 2 ms 980 KB Output is correct
17 Correct 55 ms 3928 KB Output is correct
18 Correct 52 ms 3904 KB Output is correct
19 Correct 52 ms 4128 KB Output is correct
20 Correct 53 ms 4172 KB Output is correct
21 Correct 52 ms 4164 KB Output is correct
22 Correct 62 ms 5208 KB Output is correct
23 Correct 48 ms 3516 KB Output is correct
24 Correct 52 ms 3788 KB Output is correct
25 Correct 43 ms 3144 KB Output is correct
26 Correct 44 ms 3344 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 43 ms 3200 KB Output is correct
11 Correct 7 ms 1716 KB Output is correct
12 Correct 43 ms 3104 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 42 ms 3060 KB Output is correct
15 Correct 42 ms 3180 KB Output is correct
16 Correct 2 ms 980 KB Output is correct
17 Correct 55 ms 3928 KB Output is correct
18 Correct 52 ms 3904 KB Output is correct
19 Correct 52 ms 4128 KB Output is correct
20 Correct 53 ms 4172 KB Output is correct
21 Correct 52 ms 4164 KB Output is correct
22 Correct 62 ms 5208 KB Output is correct
23 Correct 48 ms 3516 KB Output is correct
24 Correct 52 ms 3788 KB Output is correct
25 Correct 43 ms 3144 KB Output is correct
26 Correct 44 ms 3344 KB Output is correct
27 Runtime error 2 ms 596 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 9 ms 9684 KB Output is correct
3 Correct 26 ms 13616 KB Output is correct
4 Correct 20 ms 13420 KB Output is correct
5 Correct 32 ms 17984 KB Output is correct
6 Correct 30 ms 17332 KB Output is correct
7 Correct 35 ms 17856 KB Output is correct
8 Correct 33 ms 17840 KB Output is correct
9 Runtime error 23 ms 6472 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2132 KB Output is correct
2 Correct 22 ms 2636 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 67 ms 7272 KB Output is correct
6 Correct 68 ms 7272 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Runtime error 46 ms 11052 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -