Submission #56578535

Source Code Expand

#include<bits/stdc++.h>
#define lc(p) ((p)*2)
#define rc(p) ((p)*2+1)
#define mkpr make_pair
#define LL long long
using namespace std;
inline LL read() {
    char ch=getchar();
    LL x=0;
    bool t=0;
    while(ch<'0'||ch>'9')   t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return t?-x:x;
}
int n,k,a[200005],b[200005],c[200005];
LL dp[200005][15];
bool cmp(int x,int y){
	return b[x]*(a[y]-1)>b[y]*(a[x]-1);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		c[i]=i;
	}
	sort(c+1,c+1+n,cmp);
	for(int i=1;i<=n;i++){
		dp[i-1][0]=1;
		for(int j=1;j<=k;j++){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*a[c[i]]+b[c[i]]);
		}
	}
	cout<<dp[n][k];
	return 0;
}

Submission Info

Submission Time
Task F - Maximum Composition
User Lotus_Land
Language C++ 20 (gcc 12.2)
Score 500
Code Size 751 Byte
Status AC
Exec Time 69 ms
Memory 29392 KiB

Judge Result

Set Name Sample All After Contest
Score / Max Score 0 / 0 500 / 500 0 / 0
Status
AC × 2
AC × 36
AC × 1
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 02_maximum_00.txt, 02_maximum_01.txt, 02_maximum_02.txt, 02_maximum_03.txt, 02_maximum_04.txt, 03_handmade_00.txt, 03_handmade_01.txt, 03_handmade_02.txt, 03_handmade_03.txt, 03_handmade_04.txt, 03_handmade_05.txt, 03_handmade_06.txt, 03_handmade_07.txt, 03_handmade_08.txt, 03_handmade_09.txt, 03_handmade_10.txt, 03_handmade_11.txt, 03_handmade_12.txt, 03_handmade_13.txt
After Contest 04_after_contest_00.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3504 KiB
00_sample_01.txt AC 1 ms 3656 KiB
01_random_00.txt AC 66 ms 28472 KiB
01_random_01.txt AC 64 ms 27472 KiB
01_random_02.txt AC 33 ms 15752 KiB
01_random_03.txt AC 36 ms 17000 KiB
01_random_04.txt AC 52 ms 23300 KiB
01_random_05.txt AC 68 ms 29044 KiB
01_random_06.txt AC 39 ms 18496 KiB
01_random_07.txt AC 48 ms 21812 KiB
01_random_08.txt AC 36 ms 17148 KiB
01_random_09.txt AC 60 ms 26404 KiB
01_random_10.txt AC 47 ms 21372 KiB
01_random_11.txt AC 53 ms 23872 KiB
01_random_12.txt AC 68 ms 29208 KiB
01_random_13.txt AC 65 ms 28724 KiB
01_random_14.txt AC 64 ms 28068 KiB
02_maximum_00.txt AC 69 ms 29308 KiB
02_maximum_01.txt AC 69 ms 29304 KiB
02_maximum_02.txt AC 68 ms 29388 KiB
02_maximum_03.txt AC 68 ms 29320 KiB
02_maximum_04.txt AC 68 ms 29332 KiB
03_handmade_00.txt AC 57 ms 29392 KiB
03_handmade_01.txt AC 53 ms 29232 KiB
03_handmade_02.txt AC 53 ms 29212 KiB
03_handmade_03.txt AC 49 ms 29324 KiB
03_handmade_04.txt AC 64 ms 29304 KiB
03_handmade_05.txt AC 64 ms 29304 KiB
03_handmade_06.txt AC 55 ms 29240 KiB
03_handmade_07.txt AC 55 ms 29316 KiB
03_handmade_08.txt AC 68 ms 29236 KiB
03_handmade_09.txt AC 68 ms 29236 KiB
03_handmade_10.txt AC 65 ms 29368 KiB
03_handmade_11.txt AC 58 ms 29392 KiB
03_handmade_12.txt AC 1 ms 3524 KiB
03_handmade_13.txt AC 1 ms 3588 KiB
04_after_contest_00.txt AC 1 ms 3508 KiB