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 |
|
|
|
|
|
|
|
|
|
|
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 |