답안 #718651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718651	2023-04-04T13:10:41 Z	vinnipuh01	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1949 ms	984780 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1906 ms	984664 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	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	-

답안 #718651

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0