oj.uz

Submission #718855

# Submission time Handle Problem Language Result Execution time Memory
718855 2023-04-05T02:23:02 Z vinnipuh01 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1032 ms 984752 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 ];

bool cmp( pair<int, int> a, pair<int, int> b ) {
	if ( a.first - a.second == b.first - b.second ) {
		return a.first < b.first;
	}
	return ( a.first - a.second ) < ( b.first - b.second );
}

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, cmp );
	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 ++ ) {
				if ( j <= k )
					dp[ i ][ j ][ j ] = min( dp[ i - 1 ][ j ][ j ], dp[ i - 1 ][ j - 1 ][ j - 1 ] + a[ i ].first / j );
				else
					dp[ i ][ j ][ k ] = min( dp[ i - 1 ][ j ][ k ], dp[ i - 1 ][ j - 1 ][ k ] + a[ i ].second / ( k + 1 ) );
			}
		}
//		cout << k << " - " << dp[ n ][ m ][ k ] << "\n";
		ans = min( ans, dp[ n ][ m ][ k ] );
	}
	cout << fixed << setprecision( 4 ) << ans;
}

Compilation message

Main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | 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 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 490 ms 984604 KB Output is correct
6 Correct 517 ms 984624 KB Output is correct
7 Correct 656 ms 984748 KB Output is correct
8 Correct 842 ms 984752 KB Output is correct
9 Correct 1006 ms 984664 KB Output is correct
10 Correct 775 ms 984668 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 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 490 ms 984604 KB Output is correct
6 Correct 517 ms 984624 KB Output is correct
7 Correct 656 ms 984748 KB Output is correct
8 Correct 842 ms 984752 KB Output is correct
9 Correct 1006 ms 984664 KB Output is correct
10 Correct 775 ms 984668 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 486 ms 984664 KB Output is correct
13 Correct 486 ms 984724 KB Output is correct
14 Correct 476 ms 984604 KB Output is correct
15 Correct 738 ms 984668 KB Output is correct
16 Correct 802 ms 984668 KB Output is correct
17 Correct 788 ms 984744 KB Output is correct
18 Correct 997 ms 984692 KB Output is correct
19 Correct 1032 ms 984668 KB Output is correct
20 Correct 1031 ms 984704 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 592 KB Output is correct
7 Incorrect 1 ms 592 KB Output isn't correct
8 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 592 KB Output is correct
7 Incorrect 1 ms 592 KB Output isn't correct
8 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 592 KB Output is correct
7 Incorrect 1 ms 592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1029 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 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 490 ms 984604 KB Output is correct
6 Correct 517 ms 984624 KB Output is correct
7 Correct 656 ms 984748 KB Output is correct
8 Correct 842 ms 984752 KB Output is correct
9 Correct 1006 ms 984664 KB Output is correct
10 Correct 775 ms 984668 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 486 ms 984664 KB Output is correct
13 Correct 486 ms 984724 KB Output is correct
14 Correct 476 ms 984604 KB Output is correct
15 Correct 738 ms 984668 KB Output is correct
16 Correct 802 ms 984668 KB Output is correct
17 Correct 788 ms 984744 KB Output is correct
18 Correct 997 ms 984692 KB Output is correct
19 Correct 1032 ms 984668 KB Output is correct
20 Correct 1031 ms 984704 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 592 KB Output is correct
27 Incorrect 1 ms 592 KB Output isn't correct
28 Halted 0 ms 0 KB -