oj.uz

Submission #718651

# Submission time Handle Problem Language Result Execution time Memory
718651 2023-04-04T13:10:41 Z vinnipuh01 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1949 ms 984780 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int double
#define sqrt sqrtl

using namespace std;

const long long oo = 1e9;

double sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;


    freopen ( "sum.in", "r", stdin )
*/

long long n, m;
pair<int, int> a[ 501 ];
int dp[ 501 ][ 501 ][ 501 ];

main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( long long i = 1; i <= n; i ++ ) {
		cin >> a[ i ].second >> a[ i ].first;
		if ( a[ i ].first == -1 )
			a[ i ].first = oo;
	}
	ans = oo;
	sort( a + 1, a + n + 1 );
	for ( long long t = 0; t <= n; t ++ ) {
		for ( long long i = 0; i <= n; i ++ )
			for ( long long j = 0; j <= n; j ++ )
				dp[ t ][ i ][ j ] = oo;
		dp[ t ][ 0 ][ 0 ] = 0;
	}
	for ( long long k = 0; k <= m; k ++ ) {
		for ( long long i = 1; i <= n; i ++ ) {
			for ( long long j = 1; j <= min( i, m ); j ++ ) {
				dp[ i ][ j ][ 0 ] = min( dp[ i - 1 ][ j ][ 0 ], dp[ i - 1 ][ j - 1 ][ 0 ] + a[ i ].second / ( k + 1 ) );
				dp[ i ][ j ][ min( k, i ) ] = min( dp[ i - 1 ][ j ][ min( k, i ) ], min( dp[ i - 1 ][ j - 1 ][ min( k, i ) ] + a[ i ].second / ( k + 1 ), dp[ i - 1 ][ j - 1 ][ i - 1 ] + a[ i ].first / i ) );
			}
		}
//		cout << k << " - " << dp[ n ][ m ][ k ] << "\n";
		ans = min( ans, dp[ n ][ m ][ k ] );
	}
	cout << fixed << setprecision( 4 ) << ans;
}

Compilation message

Main.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main () {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 393 ms 984680 KB Output is correct
6 Correct 549 ms 984748 KB Output is correct
7 Correct 958 ms 984728 KB Output is correct
8 Correct 1458 ms 984652 KB Output is correct
9 Correct 1949 ms 984672 KB Output is correct
10 Correct 1386 ms 984664 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 393 ms 984680 KB Output is correct
6 Correct 549 ms 984748 KB Output is correct
7 Correct 958 ms 984728 KB Output is correct
8 Correct 1458 ms 984652 KB Output is correct
9 Correct 1949 ms 984672 KB Output is correct
10 Correct 1386 ms 984664 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 790 ms 984668 KB Output is correct
13 Correct 669 ms 984668 KB Output is correct
14 Correct 642 ms 984668 KB Output is correct
15 Correct 1390 ms 984672 KB Output is correct
16 Correct 1398 ms 984664 KB Output is correct
17 Correct 1390 ms 984780 KB Output is correct
18 Correct 1895 ms 984608 KB Output is correct
19 Correct 1905 ms 984692 KB Output is correct
20 Correct 1837 ms 984728 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 560 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 560 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 560 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1906 ms 984664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 393 ms 984680 KB Output is correct
6 Correct 549 ms 984748 KB Output is correct
7 Correct 958 ms 984728 KB Output is correct
8 Correct 1458 ms 984652 KB Output is correct
9 Correct 1949 ms 984672 KB Output is correct
10 Correct 1386 ms 984664 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 790 ms 984668 KB Output is correct
13 Correct 669 ms 984668 KB Output is correct
14 Correct 642 ms 984668 KB Output is correct
15 Correct 1390 ms 984672 KB Output is correct
16 Correct 1398 ms 984664 KB Output is correct
17 Correct 1390 ms 984780 KB Output is correct
18 Correct 1895 ms 984608 KB Output is correct
19 Correct 1905 ms 984692 KB Output is correct
20 Correct 1837 ms 984728 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Incorrect 1 ms 560 KB Output isn't correct
30 Halted 0 ms 0 KB -