oj.uz

답안 #778385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778385 2023-07-10T09:02:59 Z lollipop 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 25868 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 , h[ 5000 ][ 200 ] , v[ 5000 ][ 200 ] ;
vector < int > dp[ 201 ] ;
vector < int > lst , nw ;  
void calculate_dp( int pos ){
	 nw.clear() ; lst.clear() ;
	 FOR( i , c ) lst.pb( 0 ) , nw.pb( INT_MAX ) ;
	 int val = 0 ; 
	 for( int j = pos - 1 ; j >= 0 ; j -- ){
	 	val = val + h[ r - 1 ][ j ] ; 
	 	lst[ j ] = val ; 
	 }
	 val = 0 ;
	 for( int j = pos ; j < c - 1 ; j ++ ){
	 	val = val + h[ r - 1 ][ j ] ;
	 	lst[ j + 1 ] = val ; 
	 }
	 dp[ pos ].clear() ;
	 for( int i = r - 2 ; i >= 0 ; i -- ){
	 	FOR( i , c ) nw[ i ] = INT_MAX ;  
	 	int val = INT_MAX ; 
		for( int j = 0 ; j < c ; j ++ ){
	 		val = min( val , lst[ j ] + v[ i ][ j ] ) ;
			nw[ j ] = val ;
			if( j != c - 1 ) 
			val = val + h[ i ][ j ] ; 
		}
		val = INT_MAX ; 
	 	for( int j = c - 1 ; j >= 0 ; j -- ){
	 		val = min( val , lst[ j ] + v[ i ][ j ] ) ;
	 		nw[ j ] = min( nw[ j ] , val ) ;
	 		if( j != 0 )
	 		val = val + h[ i ][ j - 1 ] ; 
		}
	 	
	 	if( i == 0 ){
	 		for( auto x : nw ) dp[ pos ].pb( x ) ;
		}
		swap( lst , nw ) ; 
	 }
	 
}
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 ; 
	 FOR( i , C ) 
	 calculate_dp( i ) ;
}
void changeH(int P, int Q, int W){
	 h[ P ][ Q ] = W ;
	 FOR( i , c ) calculate_dp( i ) ; 
}
void changeV(int P, int Q, int W){
	 v[ P ][ Q ] = W ;
	 FOR( i , c ) calculate_dp( i ) ; 	 
}
int escape(int V1, int V2){
	return dp[ V2 ][ V1 ] ;
}


//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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8168 KB Output is correct
2 Correct 16 ms 8076 KB Output is correct
3 Correct 70 ms 10912 KB Output is correct
4 Correct 16 ms 8148 KB Output is correct
5 Correct 16 ms 8148 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 56 ms 2760 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 772 KB Output is correct
2 Correct 304 ms 748 KB Output is correct
3 Correct 434 ms 764 KB Output is correct
4 Correct 425 ms 724 KB Output is correct
5 Correct 420 ms 764 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1590 ms 680 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 16032 KB Output is correct
2 Correct 40 ms 15956 KB Output is correct
3 Correct 52 ms 15956 KB Output is correct
4 Correct 82 ms 17384 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 430 ms 760 KB Output is correct
2 Correct 306 ms 772 KB Output is correct
3 Correct 458 ms 768 KB Output is correct
4 Correct 466 ms 764 KB Output is correct
5 Correct 424 ms 760 KB Output is correct
6 Correct 48 ms 15956 KB Output is correct
7 Correct 39 ms 15956 KB Output is correct
8 Correct 48 ms 16032 KB Output is correct
9 Correct 81 ms 17352 KB Output is correct
10 Correct 16 ms 8148 KB Output is correct
11 Correct 16 ms 8144 KB Output is correct
12 Correct 71 ms 10928 KB Output is correct
13 Correct 16 ms 8184 KB Output is correct
14 Correct 16 ms 8144 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 56 ms 2744 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1587 ms 776 KB Output is correct
28 Execution timed out 20056 ms 19772 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 427 ms 776 KB Output is correct
2 Correct 311 ms 748 KB Output is correct
3 Correct 438 ms 764 KB Output is correct
4 Correct 430 ms 760 KB Output is correct
5 Correct 417 ms 780 KB Output is correct
6 Correct 47 ms 15956 KB Output is correct
7 Correct 56 ms 16008 KB Output is correct
8 Correct 51 ms 16028 KB Output is correct
9 Correct 81 ms 17316 KB Output is correct
10 Correct 20 ms 8148 KB Output is correct
11 Correct 16 ms 8148 KB Output is correct
12 Correct 69 ms 10832 KB Output is correct
13 Correct 18 ms 8184 KB Output is correct
14 Correct 16 ms 8152 KB Output is correct
15 Correct 3103 ms 25868 KB Output is correct
16 Execution timed out 20067 ms 23972 KB Time limit exceeded
17 Halted 0 ms 0 KB -