Submission #1970688


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define FOR(i,s,e) for(int i = (s);i <= (e);i++)

int N;
int K;

int C[2010];
int G[2010];

vector<int> books[20];

vector<int> boxs[20];

int dp[20][2010];

int main()
{
	cin >> N >> K;
	FOR(i,1,N)
	{
		cin >> C[i];
		cin >> G[i];
		books[G[i]].push_back(C[i]);
	}

	FOR(i,1,10)
	{
		sort(books[i].begin(),books[i].end(),greater<int>());
	}

	FOR(i,1,10)
	{
		boxs[i].resize(books[i].size() + 1,0);
		FOR(j,1,books[i].size())
		{
			boxs[i][j] = boxs[i][j - 1] + books[i][j - 1];
		}
	}

	FOR(i,1,10)
	{
		FOR(j,0,K)
		{
			dp[i][j] = dp[i - 1][j];


			FOR(k,1,boxs[i].size() - 1)
			{
				if(j - k >= 0)
				{
					dp[i][j] = max(dp[i][j],dp[i - 1][j - k] + boxs[i][k] + k * (k - 1));
				}
			}
		}
	}
	
	cout << dp[10][K] << endl;
	return 0;


}

Submission Info

Submission Time
Task B - 古本屋 (Books)
User niuez
Language C++14 (GCC 5.4.1)
Score 100
Code Size 897 Byte
Status AC
Exec Time 9 ms
Memory 384 KB

Judge Result

Set Name set01 set02 set03 set04 set05 set06 set07 set08 set09 set10
Score / Max Score 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
set01 01
set02 02
set03 03
set04 04
set05 05
set06 06
set07 07
set08 08
set09 09
set10 10
Case Name Status Exec Time Memory
01 AC 1 ms 256 KB
02 AC 6 ms 384 KB
03 AC 8 ms 384 KB
04 AC 7 ms 384 KB
05 AC 1 ms 256 KB
06 AC 8 ms 384 KB
07 AC 3 ms 384 KB
08 AC 9 ms 384 KB
09 AC 5 ms 384 KB
10 AC 7 ms 384 KB