diff options
Diffstat (limited to 'works/life/algorithm-contest-2')
35 files changed, 0 insertions, 591 deletions
diff --git a/works/life/algorithm-contest-2/README.md b/works/life/algorithm-contest-2/README.md deleted file mode 100644 index ce3292d..0000000 --- a/works/life/algorithm-contest-2/README.md +++ /dev/null @@ -1,9 +0,0 @@ -2020.10.25
-
-此文件夹包含第二届数计学院算法大赛相关的文件。
-
-- `solution`里是参考答案。
-- `generator`里是测试数据生成器。
-- `gen.ps1`和`pack.ps1`为生成测试数据用的便捷脚本。
-- `output.zip`为最终的测试数据。
-- `problems.pdf`为本次比赛的题目。
diff --git a/works/life/algorithm-contest-2/gen.ps1 b/works/life/algorithm-contest-2/gen.ps1 deleted file mode 100644 index 60b88b2..0000000 --- a/works/life/algorithm-contest-2/gen.ps1 +++ /dev/null @@ -1,39 +0,0 @@ -Push-Location solution
-
-foreach ($problem in 1..5) {
- clang-cl "$problem.cpp" /O2 "-fsanitize=address,undefined"
-}
-
-Pop-Location
-
-Remove-Item -Recurse output
-
-mkdir .\output
-
-$time_output = @()
-
-foreach ($problem in 1..5) {
- mkdir output/$problem
- foreach ($genfile in Get-ChildItem "generator/$problem") {
- if ($genfile.Name -match "(.+)\.in") {
- $genfile_id = $Matches[1]
- Copy-Item $genfile output/$problem
- }
- elseif ($genfile.Name -match "(.+)\.cpp") {
- $genfile_id = $Matches[1]
- Push-Location "generator/$problem"
- clang-cl $genfile.Name /O2 "-fsanitize=address,undefined"
- Pop-Location
- & "./generator/$problem/$genfile_id.exe" > "./output/$problem/$genfile_id.in"
- }
- $time = (Measure-Command {
- Get-Content "./output/$problem/$genfile_id.in" | & "./solution/$problem.exe" > "./output/$problem/$genfile_id.out"
- }).TotalSeconds
-
- $time_output += "Problem $problem test point $genfile_id time: $time s."
- }
-}
-
-foreach ($line in $time_output) {
- Write-Output $line
-}
diff --git a/works/life/algorithm-contest-2/generator/1/1.in b/works/life/algorithm-contest-2/generator/1/1.in deleted file mode 100644 index 38f8fd6..0000000 --- a/works/life/algorithm-contest-2/generator/1/1.in +++ /dev/null @@ -1 +0,0 @@ -8 3
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/1/2.in b/works/life/algorithm-contest-2/generator/1/2.in deleted file mode 100644 index f4eea7b..0000000 --- a/works/life/algorithm-contest-2/generator/1/2.in +++ /dev/null @@ -1 +0,0 @@ -4 4
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/1/3.in b/works/life/algorithm-contest-2/generator/1/3.in deleted file mode 100644 index 11ab954..0000000 --- a/works/life/algorithm-contest-2/generator/1/3.in +++ /dev/null @@ -1 +0,0 @@ -4 6
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/1/4.in b/works/life/algorithm-contest-2/generator/1/4.in deleted file mode 100644 index 11c3433..0000000 --- a/works/life/algorithm-contest-2/generator/1/4.in +++ /dev/null @@ -1 +0,0 @@ -8 2
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/1/5.in b/works/life/algorithm-contest-2/generator/1/5.in deleted file mode 100644 index fda96a5..0000000 --- a/works/life/algorithm-contest-2/generator/1/5.in +++ /dev/null @@ -1 +0,0 @@ -88888 5
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/2/1.in b/works/life/algorithm-contest-2/generator/2/1.in deleted file mode 100644 index 37ba146..0000000 --- a/works/life/algorithm-contest-2/generator/2/1.in +++ /dev/null @@ -1,2 +0,0 @@ -4
-6 2 9 1
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/2/2.in b/works/life/algorithm-contest-2/generator/2/2.in deleted file mode 100644 index 01faa33..0000000 --- a/works/life/algorithm-contest-2/generator/2/2.in +++ /dev/null @@ -1,2 +0,0 @@ -3
-13 22 11
diff --git a/works/life/algorithm-contest-2/generator/2/3.cpp b/works/life/algorithm-contest-2/generator/2/3.cpp deleted file mode 100644 index 0eeadd1..0000000 --- a/works/life/algorithm-contest-2/generator/2/3.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include <iostream>
-#include <random>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 5000);
- const int SIZE = 5000;
- cout << SIZE << '\n';
- for (int i = 0; i < SIZE; i++) {
- cout << distribution(engine) << ' ';
- }
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/2/4.cpp b/works/life/algorithm-contest-2/generator/2/4.cpp deleted file mode 100644 index 08d5c14..0000000 --- a/works/life/algorithm-contest-2/generator/2/4.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include <iostream>
-#include <random>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 9999);
- const int SIZE = 9999;
- cout << SIZE << '\n';
- for (int i = 0; i < SIZE; i++) {
- cout << distribution(engine) << ' ';
- }
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/2/5.cpp b/works/life/algorithm-contest-2/generator/2/5.cpp deleted file mode 100644 index bae2a90..0000000 --- a/works/life/algorithm-contest-2/generator/2/5.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include <iostream>
-#include <random>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 9999);
- const int SIZE = 9998;
- cout << SIZE << '\n';
- for (int i = 0; i < SIZE; i++) {
- cout << distribution(engine) << ' ';
- }
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/3/1.in b/works/life/algorithm-contest-2/generator/3/1.in deleted file mode 100644 index 170d639..0000000 --- a/works/life/algorithm-contest-2/generator/3/1.in +++ /dev/null @@ -1,4 +0,0 @@ -3
-#..
-...
-#.#
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/3/2.in b/works/life/algorithm-contest-2/generator/3/2.in deleted file mode 100644 index 7cefeb0..0000000 --- a/works/life/algorithm-contest-2/generator/3/2.in +++ /dev/null @@ -1,5 +0,0 @@ -4
-#...
-....
-#.#.
-....
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/3/3.in b/works/life/algorithm-contest-2/generator/3/3.in deleted file mode 100644 index 51fff91..0000000 --- a/works/life/algorithm-contest-2/generator/3/3.in +++ /dev/null @@ -1,6 +0,0 @@ -5
-#....
-.....
-.....
-.....
-.....
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/3/4.cpp b/works/life/algorithm-contest-2/generator/3/4.cpp deleted file mode 100644 index ed2fbb6..0000000 --- a/works/life/algorithm-contest-2/generator/3/4.cpp +++ /dev/null @@ -1,18 +0,0 @@ -#include <iostream>
-#include <random>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 100);
- const int SIZE = 100;
- cout << SIZE << '\n';
- for (int i = 0; i < SIZE; i++) {
- for (int j = 0; j < SIZE; j++) {
- cout << (distribution(engine) > 90 ? '#' : '.');
- }
- cout << '\n';
- }
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/3/5.cpp b/works/life/algorithm-contest-2/generator/3/5.cpp deleted file mode 100644 index bf1d14c..0000000 --- a/works/life/algorithm-contest-2/generator/3/5.cpp +++ /dev/null @@ -1,18 +0,0 @@ -#include <iostream>
-#include <random>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 100);
- const int SIZE = 100;
- cout << SIZE << '\n';
- for (int i = 0; i < SIZE; i++) {
- for (int j = 0; j < SIZE; j++) {
- cout << (distribution(engine) < 75 ? '#' : '.');
- }
- cout << '\n';
- }
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/4/1.in b/works/life/algorithm-contest-2/generator/4/1.in deleted file mode 100644 index feef14b..0000000 --- a/works/life/algorithm-contest-2/generator/4/1.in +++ /dev/null @@ -1,3 +0,0 @@ -2 10
-6 5
-5 6
diff --git a/works/life/algorithm-contest-2/generator/4/2.in b/works/life/algorithm-contest-2/generator/4/2.in deleted file mode 100644 index d72e475..0000000 --- a/works/life/algorithm-contest-2/generator/4/2.in +++ /dev/null @@ -1,4 +0,0 @@ -3 20
-1 2
-2 1
-3 4
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/4/3.in b/works/life/algorithm-contest-2/generator/4/3.in deleted file mode 100644 index 60d56de..0000000 --- a/works/life/algorithm-contest-2/generator/4/3.in +++ /dev/null @@ -1,4 +0,0 @@ -3 1
-4 5
-8 6
-7 7
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/4/4.cpp b/works/life/algorithm-contest-2/generator/4/4.cpp deleted file mode 100644 index fc0de0b..0000000 --- a/works/life/algorithm-contest-2/generator/4/4.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <iostream>
-#include <random>
-#include <vector>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 1000);
- const int SIZE = 100;
- std::vector<int> b;
-
- for (int i = 0; i < SIZE * 2; i++) {
- b.push_back(distribution(engine));
- }
-
- long long sum = 0;
- for (int i = 0; i < SIZE; i++) {
- sum += b[i * 2] * b[i * 2 + 1];
- }
-
- cout << SIZE << ' ' << (sum + 10) << '\n';
-
- for (int i = 0; i < SIZE; i++) {
- cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
- }
-
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/4/5.cpp b/works/life/algorithm-contest-2/generator/4/5.cpp deleted file mode 100644 index 518a4aa..0000000 --- a/works/life/algorithm-contest-2/generator/4/5.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <iostream>
-#include <random>
-#include <vector>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 10000);
- const int SIZE = 600;
- std::vector<int> b;
-
- for (int i = 0; i < SIZE * 2; i++) {
- b.push_back(distribution(engine));
- }
-
- long long sum = 0;
- for (int i = 0; i < SIZE; i++) {
- sum += b[i * 2] * b[i * 2 + 1];
- }
-
- cout << SIZE << ' ' << 5000 << '\n';
-
- for (int i = 0; i < SIZE; i++) {
- cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
- }
-
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/4/6.cpp b/works/life/algorithm-contest-2/generator/4/6.cpp deleted file mode 100644 index b4bdb00..0000000 --- a/works/life/algorithm-contest-2/generator/4/6.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <iostream>
-#include <random>
-#include <vector>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> distribution(1, 10000);
- const int SIZE = 100;
- std::vector<int> b;
-
- for (int i = 0; i < SIZE * 2; i++) {
- b.push_back(distribution(engine));
- }
-
- long long sum = 0;
- for (int i = 0; i < SIZE; i++) {
- sum += b[i * 2] * b[i * 2 + 1];
- }
-
- cout << SIZE << ' ' << 5000 << '\n';
-
- for (int i = 0; i < SIZE; i++) {
- cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
- }
-
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/generator/5/1.in b/works/life/algorithm-contest-2/generator/5/1.in deleted file mode 100644 index a1dfd91..0000000 --- a/works/life/algorithm-contest-2/generator/5/1.in +++ /dev/null @@ -1,2 +0,0 @@ -5 3
-6 1 2 3 4
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/5/2.in b/works/life/algorithm-contest-2/generator/5/2.in deleted file mode 100644 index 7c0d388..0000000 --- a/works/life/algorithm-contest-2/generator/5/2.in +++ /dev/null @@ -1,2 +0,0 @@ -6 8
-1 9 5 4 3 6
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/generator/5/3.cpp b/works/life/algorithm-contest-2/generator/5/3.cpp deleted file mode 100644 index 62d18c4..0000000 --- a/works/life/algorithm-contest-2/generator/5/3.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include <iostream>
-#include <random>
-#include <vector>
-
-using std::cout;
-
-int main() {
- std::default_random_engine engine(std::random_device{}());
- std::uniform_int_distribution<int> insert_distribution(0, 997);
- std::uniform_int_distribution<int> distribution(1, 100000);
- const int SIZE = 1000;
- std::vector<int> v;
-
- for (int i = 0; i < SIZE - 1; i++) {
- v.push_back(distribution(engine));
- }
-
- int K = 320;
-
- int a_index = insert_distribution(engine);
- int a = v[a_index];
- int b_index = insert_distribution(engine);
- while (b_index == a_index) {
- b_index = insert_distribution(engine);
- }
- int b = v[b_index];
-
- int c_index = insert_distribution(engine);
- while (c_index == a_index && c_index == b_index) {
- c_index = insert_distribution(engine);
- }
- int c = v[c_index];
-
- int d = (((-a - b - c) % K + K) % K) + 20 * K;
-
- int d_index = insert_distribution(engine);
-
- v.insert(v.cbegin() + d_index, c);
-
- cout << SIZE << ' ' << K << '\n';
-
- for (int i = 0; i < SIZE; i++) {
- cout << v[i] << ' ';
- }
-
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/output.zip b/works/life/algorithm-contest-2/output.zip Binary files differdeleted file mode 100644 index 9ef7e40..0000000 --- a/works/life/algorithm-contest-2/output.zip +++ /dev/null diff --git a/works/life/algorithm-contest-2/pack.ps1 b/works/life/algorithm-contest-2/pack.ps1 deleted file mode 100644 index 6d77d81..0000000 --- a/works/life/algorithm-contest-2/pack.ps1 +++ /dev/null @@ -1,6 +0,0 @@ -foreach ($problem in 1..5) {
- Push-Location "output/$problem"
- 7z a -tzip "$problem.zip" *
- Move-Item "$problem.zip" ..
- Pop-Location
-}
diff --git a/works/life/algorithm-contest-2/problems.pdf b/works/life/algorithm-contest-2/problems.pdf Binary files differdeleted file mode 100644 index dfb7df1..0000000 --- a/works/life/algorithm-contest-2/problems.pdf +++ /dev/null diff --git a/works/life/algorithm-contest-2/solution/1.cpp b/works/life/algorithm-contest-2/solution/1.cpp deleted file mode 100644 index 2689f9d..0000000 --- a/works/life/algorithm-contest-2/solution/1.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <iostream>
-#include <cstdio>
-#include <cstring>
-#include <algorithm>
-#include <vector>
-#include <queue>
-#include <stack>
-#include <set>
-#include <map>
-#include <cmath>
-#include <unordered_map>
-#include <unordered_set>
-#include <string>
-#include <sstream>
-#include <climits>
-#define x first
-#define y second
-#define pub push_back
-#define mp make_pair
-#define ll long long
-using namespace std;
-
-int x, y;
-
-int main(void) {
- cin >> x >> y;
- int ans = x;
- while (x >= y) {
- ans += x / y;
- x = x / y + x % y;
- }
- cout << ans;
- return 0;
-}
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/solution/2.cpp b/works/life/algorithm-contest-2/solution/2.cpp deleted file mode 100644 index 4410da0..0000000 --- a/works/life/algorithm-contest-2/solution/2.cpp +++ /dev/null @@ -1,41 +0,0 @@ -#define _CRT_SECURE_NO_WARNINGS
-#include <iostream>
-#include <cstdio>
-#include <cstring>
-#include <algorithm>
-#include <vector>
-#include <queue>
-#include <stack>
-#include <set>
-#include <map>
-#include <cmath>
-#include <unordered_map>
-#include <unordered_set>
-#include <string>
-#include <sstream>
-#include <climits>
-#define x first
-#define y second
-#define pub push_back
-#define mp make_pair
-#define ll long long
-using namespace std;
-typedef pair<int, int> PII;
-
-const int MAXN = 1e5 + 5;
-int n, a[MAXN];
-
-int main(void) {
- cin >> n;
- for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
- sort(a + 1, a + 1 + n);
-
- int l = 1, r = n;
- ll ans = 0;
-
- while (l < r) {
- ans += (a[r--] - a[l++]);
- }
- cout << ans;
- return 0;
-}
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/solution/3.cpp b/works/life/algorithm-contest-2/solution/3.cpp deleted file mode 100644 index a97e351..0000000 --- a/works/life/algorithm-contest-2/solution/3.cpp +++ /dev/null @@ -1,77 +0,0 @@ -#include <iostream>
-#include <cstdio>
-#include <cstring>
-#include <algorithm>
-#include <vector>
-#include <queue>
-#include <stack>
-#include <set>
-#include <map>
-#include <cmath>
-#include <unordered_map>
-#include <unordered_set>
-#include <string>
-#include <sstream>
-#include <climits>
-#define x first
-#define y second
-#define pub push_back
-#define mp make_pair
-#define ll long long
-using namespace std;
-typedef pair<int, int> PII;
-
-struct node{
- int x, y;
- node(){}
- node(int _x = 0,int _y = 0): x(_x), y(_y){}
-};
-
-int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
-int n;
-vector<string> graph;
-vector<vector<int>> vis;
-
-int solve() {
- queue<node> Q;
- for(int i = 0;i < n;++i){
- for(int j = 0;j < n;++j){
- if(graph[i][j] == '#') Q.push(node(i,j));
- vis[i][j] = 0;
- }
- }
-
- if(Q.size() == n * n || Q.empty()) return -1;
-
- int dis = 0;
- while(!Q.empty()){
- int size = Q.size();
- while(size-- > 0){
- node cur = Q.front();
- Q.pop();
- for(int i = 0;i < 4;i++){
- int nextX = cur.x + dir[i][0];
- int nextY = cur.y + dir[i][1];
- if(nextX > -1 && nextX < n && nextY > -1 && nextY < n && graph[nextX][nextY] == '.' && !vis[nextX][nextY]){
- vis[nextX][nextY] = 1;
- Q.push(node(nextX,nextY));
- }
- }
- }
- if(!Q.empty()) dis += 1;
- }
- return dis;
-}
-
-int main(void) {
- cin >> n;
- string line;
- vis.resize(n + 1, vector<int>(n + 1));
- for (int i = 0; i < n; i++) {
- cin >> line;
- graph.push_back(line);
- }
-
- cout << solve();
- return 0;
-}
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/solution/4.cpp b/works/life/algorithm-contest-2/solution/4.cpp deleted file mode 100644 index 93c9190..0000000 --- a/works/life/algorithm-contest-2/solution/4.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#define _CRT_SECURE_NO_WARNINGS
-#include <iostream>
-#include <cstdio>
-#include <cstring>
-#include <algorithm>
-#include <vector>
-#include <set>
-#include <map>
-#include <cmath>
-#include <unordered_map>
-#define x first
-#define y second
-#define pub push_back
-#define MP make_pair
-#define LL long long
-using namespace std;
-typedef pair<int, int> PII;
-
-const int MAXN = 1e5 + 5;
-int n, k, h[MAXN], w[MAXN];
-
-bool check(int m) {
- if (m == 0) return true;
- int cnt = 0;
- for (int i = 0; i < n; i++) {
- cnt += (h[i] / m) * (w[i] / m);
- }
- return cnt >= k;
-}
-
-int main(void) {
- cin >> n >> k;
- int mx = 0;
- for (int i = 0; i < n; i++) {
- scanf("%d", &h[i]);
- scanf("%d", &w[i]);
- mx = max(mx, max(h[i], w[i]));
- }
-
- int l = 0, r = mx;
- while (l < r) {
- int m = (l + r + 1) >> 1;
- if (check(m)) l = m;
- else r = m - 1;
- }
- cout << r;
- return 0;
-}
\ No newline at end of file diff --git a/works/life/algorithm-contest-2/solution/5-bf.cpp b/works/life/algorithm-contest-2/solution/5-bf.cpp deleted file mode 100644 index f197e6b..0000000 --- a/works/life/algorithm-contest-2/solution/5-bf.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <iostream>
-
-int batteries[1000];
-
-int main(void) {
- int N, K;
- std::cin >> N >> K;
- for (int i = 0; i < N; i++)
- std::cin >> batteries[i];
-
- int max = 0;
- int max_index[4];
-
- for (int i = 0; i < N; i++) {
- for (int j = i + 1; j < N; j++) {
- for (int k = j + 1; k < N; k++) {
- for (int l = k + 1; l < N; l++) {
- int sum = batteries[i] + batteries[j] + batteries[k] + batteries[l];
- if (sum % K == 0 && sum > max) {
- max = sum;
- max_index[0] = i;
- max_index[1] = j;
- max_index[2] = k;
- max_index[3] = l;
- }
- }
- }
- }
- }
-
- std::cout << max;
-
- return 0;
-}
diff --git a/works/life/algorithm-contest-2/solution/5.cpp b/works/life/algorithm-contest-2/solution/5.cpp deleted file mode 100644 index b668f95..0000000 --- a/works/life/algorithm-contest-2/solution/5.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include <iostream>
-#include <cstdio>
-#include <cstring>
-#include <algorithm>
-#include <vector>
-#include <queue>
-#include <stack>
-#include <set>
-#include <map>
-#include <cmath>
-#include <unordered_map>
-#include <unordered_set>
-#include <string>
-#include <sstream>
-#include <climits>
-#define x first
-#define y second
-#define pub push_back
-#define mp make_pair
-#define ll long long
-using namespace std;
-typedef pair<int, int> PII;
-
-int dp[1005][5][1005];
-int n, K, a[1005];
-
-int main(void) {
- // freopen("3.in", "r", stdin);
- cin >> n >> K;
- for (int i = 1; i <= n; i++) cin >> a[i];
-
- for (int i = 0; i < 1005; i++)
- for (int j = 0; j < 4; j++)
- for (int k = 0; k < 1005; k++)
- dp[i][j][k] = INT_MIN;
-
- dp[0][0][0] = 0;
-
- for (int i = 1; i <= n; i++)
- for (int j = 0; j <= 4; j++)
- for (int k = 0; k < K; k++) {
- if (j == 0) dp[i][j][k] = dp[i - 1][j][k];
- else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][((k - a[i]) % K + K) % K] + a[i]);
- }
-
-
- cout << dp[n][4][0];
- return 0;
-}
\ No newline at end of file |