80 lines
1.3 KiB
C++
Executable File
80 lines
1.3 KiB
C++
Executable File
#include <iostream>
|
|
#include <fstream>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
ifstream input_stream;
|
|
ofstream output_stream;
|
|
|
|
|
|
|
|
int getMaxValue(int P[], int W[], int C, int N) {
|
|
int table[2][C] = {0};
|
|
|
|
for (int i = 0; i < 2; i++) {
|
|
for (int j = 0; j < C; j++) {
|
|
table[i][j] = 0;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
int *topRow;
|
|
int *bottomRow;
|
|
if (i % 2 == 0) {
|
|
topRow = table[0];
|
|
bottomRow = table[1];
|
|
} else {
|
|
topRow = table[1];
|
|
bottomRow = table[0];
|
|
}
|
|
|
|
|
|
if (1 >= W[i]) {
|
|
bottomRow[0] = max(P[i] + topRow[1 - W[i]], bottomRow[1 - 1]);
|
|
} else {
|
|
bottomRow[0] = bottomRow[1 - 1];
|
|
}
|
|
|
|
for (int w = 1; w < C; w++) {
|
|
if (w + 1 > W[i]) {
|
|
bottomRow[w] = max(P[i] + topRow[(w + 1) - W[i]], topRow[w]);
|
|
} else {
|
|
bottomRow[w] = topRow[w];
|
|
}
|
|
|
|
for (int y = 0; y < 2; y++) {
|
|
for (int x = 0; x < C; x++) {
|
|
cout << table[y][x] << " ";
|
|
}
|
|
cout << endl;
|
|
}
|
|
// string tmp;
|
|
// cin >> tmp;
|
|
}
|
|
}
|
|
|
|
return max(table[0][C-1], table[1][C-1]);
|
|
}
|
|
|
|
|
|
int main() {
|
|
input_stream.open("input.txt");
|
|
|
|
int N, C;
|
|
input_stream >> N;
|
|
input_stream >> C;
|
|
|
|
int P[N];
|
|
int W[N];
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
input_stream >> W[i];
|
|
input_stream >> P[i];
|
|
}
|
|
|
|
cout << getMaxValue(P, W, C, N) << endl;
|
|
|
|
input_stream.close();
|
|
return 0;
|
|
} |