oj.uz

Submission #787111

# Submission time Handle Problem Language Result Execution time Memory
787111 2023-07-18T20:26:10 Z lollipop Wombats (IOI13_wombats) C++17
100 / 100
 4947 ms 190772 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 173776 KB Output is correct
2 Correct 362 ms 173884 KB Output is correct
3 Correct 396 ms 176648 KB Output is correct
4 Correct 389 ms 173884 KB Output is correct
5 Correct 356 ms 173900 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1596 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3516 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 2 ms 3588 KB Output is correct
8 Correct 2 ms 3516 KB Output is correct
9 Correct 2 ms 3540 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 58 ms 5860 KB Output is correct
12 Correct 2 ms 3540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 8388 KB Output is correct
2 Correct 101 ms 8372 KB Output is correct
3 Correct 125 ms 8396 KB Output is correct
4 Correct 122 ms 8504 KB Output is correct
5 Correct 115 ms 8404 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 394 ms 8380 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 181660 KB Output is correct
2 Correct 360 ms 181732 KB Output is correct
3 Correct 364 ms 181708 KB Output is correct
4 Correct 383 ms 183096 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 8388 KB Output is correct
2 Correct 88 ms 8376 KB Output is correct
3 Correct 142 ms 8384 KB Output is correct
4 Correct 123 ms 8380 KB Output is correct
5 Correct 115 ms 8404 KB Output is correct
6 Correct 358 ms 181720 KB Output is correct
7 Correct 356 ms 181668 KB Output is correct
8 Correct 381 ms 181664 KB Output is correct
9 Correct 389 ms 183076 KB Output is correct
10 Correct 370 ms 173876 KB Output is correct
11 Correct 351 ms 173932 KB Output is correct
12 Correct 404 ms 176636 KB Output is correct
13 Correct 370 ms 173944 KB Output is correct
14 Correct 352 ms 173876 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 2 ms 1596 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 3 ms 3520 KB Output is correct
19 Correct 2 ms 3540 KB Output is correct
20 Correct 3 ms 3540 KB Output is correct
21 Correct 3 ms 3512 KB Output is correct
22 Correct 3 ms 3540 KB Output is correct
23 Correct 3 ms 3540 KB Output is correct
24 Correct 2 ms 3540 KB Output is correct
25 Correct 64 ms 5836 KB Output is correct
26 Correct 2 ms 3540 KB Output is correct
27 Correct 398 ms 8384 KB Output is correct
28 Correct 1313 ms 186096 KB Output is correct
29 Correct 1455 ms 182372 KB Output is correct
30 Correct 1462 ms 182824 KB Output is correct
31 Correct 1346 ms 187544 KB Output is correct
32 Correct 1 ms 2104 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 8384 KB Output is correct
2 Correct 89 ms 8368 KB Output is correct
3 Correct 125 ms 8388 KB Output is correct
4 Correct 140 ms 8392 KB Output is correct
5 Correct 117 ms 8396 KB Output is correct
6 Correct 340 ms 181636 KB Output is correct
7 Correct 349 ms 181732 KB Output is correct
8 Correct 381 ms 181752 KB Output is correct
9 Correct 378 ms 183116 KB Output is correct
10 Correct 349 ms 173844 KB Output is correct
11 Correct 352 ms 173800 KB Output is correct
12 Correct 398 ms 176588 KB Output is correct
13 Correct 360 ms 173900 KB Output is correct
14 Correct 344 ms 173836 KB Output is correct
15 Correct 1651 ms 185580 KB Output is correct
16 Correct 4947 ms 189032 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1592 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 3 ms 3540 KB Output is correct
21 Correct 3 ms 3516 KB Output is correct
22 Correct 2 ms 3540 KB Output is correct
23 Correct 2 ms 3540 KB Output is correct
24 Correct 2 ms 3540 KB Output is correct
25 Correct 2 ms 3540 KB Output is correct
26 Correct 2 ms 3524 KB Output is correct
27 Correct 57 ms 5844 KB Output is correct
28 Correct 2 ms 3540 KB Output is correct
29 Correct 404 ms 8380 KB Output is correct
30 Correct 1313 ms 186128 KB Output is correct
31 Correct 4066 ms 190228 KB Output is correct
32 Correct 4213 ms 190216 KB Output is correct
33 Correct 1399 ms 182320 KB Output is correct
34 Correct 4239 ms 186460 KB Output is correct
35 Correct 1460 ms 182732 KB Output is correct
36 Correct 4285 ms 186984 KB Output is correct
37 Correct 1357 ms 187516 KB Output is correct
38 Correct 4221 ms 190772 KB Output is correct
39 Correct 1 ms 2004 KB Output is correct
40 Correct 4507 ms 186428 KB Output is correct