Submission #787111

#	Time	Username	Problem	Language	Result	Execution time	Memory
787111		lollipop	Wombats (IOI13_wombats)	C++17	100 / 100	4947 ms	190772 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#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 = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int r , c ;
int h[ 5000 ][ 200 ] , v[ 5000 ][ 200 ] ;
struct node{
	int a[ 201 ][ 201 ] ;
};
node tt[ 2010 ] ;
int opt[ 201 ][ 201 ] ;
int col[ 201 ][ 201 ] ; 
node combine( node a , node b , int hh ){
	 node res ; 
	 FOR( i , c ){
        FOR( j , c ){
            a.a[ i ][ j ] += v[ hh ][ j ] ;
        }
       }
	 // tavis tavshi mivides jerr
	 FOR( i , c ){
	 	res.a[ i ][ i ] = INT_MAX ; 
		FOR( j , c ){
	 		int cur = a.a[ i ][ j ] + b.a[ j ][ i ] ;
			if( cur < res.a[ i ][ i ] ){
				res.a[ i ][ i ] = cur ;
				opt[ i ][ i ] = j ; 
			} 
		}
	 }
	 
	 for( int move = 1 ; move < c ; move ++ ){
	 	FOR( i , c ){
	       int j = i + move ; 		
		   if( j < c ){	
		      res.a[ i ][ j ] = INT_MAX ; 
			  for( int k = opt[ i ][ j - 1 ] ; k <= opt[ i + 1 ][ j ] ; k ++ ){
		      	 int cur = a.a[ i ][ k ] + b.a[ k ][ j ] ;
		      	 if( cur < res.a[ i ][ j ] ){
		      	   res.a[ i ][ j ] = cur ;
				   opt[ i ][ j ] = k ; 	
				 }
			  }
		   }	
		   j = i - move ;
		   if( j < 0 ) continue ; 
		   res.a[ i ][ j ] = INT_MAX ;
		   for( int k = opt[ i - 1 ][ j ] ; k <= opt[ i ][ j + 1 ] ; k ++ ){
		      int cur = a.a[ i ][ k ] + b.a[ k ][ j ] ;
		      if( cur < res.a[ i ][ j ] ){
		      	 res.a[ i ][ j ] = cur ;
				 opt[ i ][ j ] = k ; 	
			  }		   	 
		   }
	 		
		 }
	 }
	 return res ; 
}
node get_pas( int l , int r ){
//	cout << l << " " << r << endl ;
	 if( l == r ){
	 	node nd ;
	 	FOR( i , c ){
	 	  nd.a[ i ][ i ] = 0 ;
	 	  int cc = 0 ; 
		  for( int j = i - 1 ; j >= 0 ; j -- ){
		  	cc += h[ l ][ j ] ;
		  	nd.a[ i ][ j ] = cc ; 
		  } 	
		  cc = 0 ; 
		  for( int j = i + 1 ; j < c ; j ++ ){
		  	cc += h[ l ][ j - 1 ] ;
		  	nd.a[ i ][ j ] = cc ; 
		  }
		}
		return nd ; 
	 }
	 int mid = ( l + r ) / 2 ;
	 node a = get_pas( l , mid ) ;
	 node b = get_pas( mid + 1 , r ) ;
	 node c = combine( a , b , mid ) ;
	 return c ;  
}
void build( int v , int l , int r ){
     if( r - l + 1 <= 10 ){
        tt[ v ] = get_pas( l , r ) ;
        return ;
	 }	 
	 int vm = ( l + r ) / 2 ; 
	 build( v + v , l , vm ) ;
	 build( v + v + 1 , vm + 1 , r ) ;
	 tt[ v ] = combine( tt[ v + v ] , tt[ v + v + 1 ] , vm ) ;
}
void upd( int v , int l , int r , int pos ){
	 if( r - l + 1 <= 10 ){
	 	tt[ v ] = get_pas( l , r ) ;
	 	return ;
	 }
	 int vm = ( l + r ) / 2 ;
	 if( vm >= pos ){
	 	upd( v + v , l , vm , pos ) ;
	 }
	 else upd( v + v + 1 , vm + 1 , r , pos ) ;
	 tt[ v ] = combine( tt[ v + v ] , tt[ v + v + 1 ] , vm ) ;
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
	 FOR( i , R ){
	 	FOR( j , C - 1 ) h[ i ][ j ] = H[ i ][ j ] ;
	 }
	 FOR( i , C ){
	 	FOR( j , R - 1 ) v[ j ][ i ] = V[ j ][ i ] ;
	 }
	 r = R , c = C ; 
//	 debug ; 
	 build( 1 , 0 , r - 1 ) ;
//	 debug ;
}
void changeH(int P, int Q, int W){
	 h[ P ][ Q ] = W ; 
	 upd( 1 , 0 , r - 1 , P ) ;
}
void changeV(int P, int Q, int W){
	 v[ P ][ Q ] = W ; 
	 upd( 1 , 0 , r - 1 , P ) ; 	 
}
int escape(int V1, int V2){
	return tt[ 1 ].a[ V1 ][ V2 ] ; 
}


// static int H[5000][200];
// static int V[5000][200];
// int main() {
//     int R, C, E, P, Q, W, V1, V2, event, i, j;

//     assert(scanf("%d%d", &R, &C) == 2);
//     for (i = 0; i < R; ++i)
//         for (j = 0; j < C-1; ++j)
//             assert(scanf("%d", &H[i][j]) == 1);
//     for (i = 0; i < R-1; ++i)
//         for (j = 0; j < C; ++j)
//             assert(scanf("%d", &V[i][j]) == 1);

//     init(R, C, H, V);
    
//     std::vector<int> answers;

//     assert(scanf("%d", &E) == 1);
//     for (i = 0; i < E; i++) {
//         assert(scanf("%d", &event) == 1);
//         if (event == 1) {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeH(P, Q, W);
//         } else if (event == 2) {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeV(P, Q, W);
//         } else if (event == 3) {
//             assert(scanf("%d%d", &V1, &V2) == 2);
//             answers.push_back(escape(V1, V2));
//         } 
//     }
//     for (int ans : answers) {
//         printf("%d\n", ans);
//     }
//     return 0;
// }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24