제출 #852320

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
852320	2023-09-21 15:16:00	adaawf	Nafta (COI15_nafta)	C++14	100 / 100	380 ms	107092 KiB

nafta

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;
int n, m, a[2005][2005], dd[2005][2005], f[2005][2005], ma = 0, mi = 999999999, c = 0;
int d[2005], res[2005], ff[2005][2005];
vector<pair<int, int>> g[2005];
void dfs(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > m || a[x][y] == -1 || dd[x][y] == 1) return;
    dd[x][y] = 1;
    ma = max(ma, y);
    mi = min(mi, y);
    c += a[x][y];
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}
void solve(int k, int l, int r, int x, int y) {
    if (l > r) return;
    int mid = (l + r) / 2, ma = 0, h = 0;
    for (int i = x; i <= min(mid, y); i++) {
        if (f[i][k - 1] - ff[i][mid] >= ma) {
            ma = f[i][k - 1] - ff[i][mid];
            h = i;
        }
    }
    f[mid][k] = ma + f[mid][1];
    res[k] = max(res[k], f[mid][k]);
    solve(k, l, mid - 1, x, h);
    solve(k, mid + 1, r, h, y);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66