oj.uz

Submission #971734

# Submission time Handle Problem Language Result Execution time Memory
971734 2024-04-29T08:23:04 Z dwuy Nafta (COI15_nafta) C++14
100 / 100
 225 ms 168540 KB 
/**   - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 2005;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, m;
int val[MX][MX];
int cost[MX][MX];
int f[MX][MX];
string a[MX];

void nhap(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] = ' ' + a[i];
    }
}

void dfs(int x, int y, int &L, int &R, int &sum){
    sum += a[x][y] - '0';
    L = min(L, y);
    R = max(R, y);
    a[x][y] = '.';
    for(int i=0; i<4; i++){
        int u = x + dx[i];
        int v = y + dy[i];
        if(u<1 || u>n || v<1 || v>m || a[u][v] == '.') continue;
        dfs(u, v, L, R, sum);
    }
}

void dwuy(int id, int l, int r, int fx, int fy){
    if(l > r) return;
    int mid = (l + r)>>1;
    pii best = {-1, 0};
    for(int i=fx; i<=min(mid, fy); i++){
        best = max(best, {f[id-1][i] + cost[i+1][mid], i});
    }
    f[id][mid] = best.fi;
    dwuy(id, l, mid-1, fx, best.se);
    dwuy(id, mid+1, r, best.se, fy);
}

void solve(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j] == '.') continue;
            int L = j, R = j, sum = 0;
            dfs(i, j, L, R, sum);
            val[L][R] += sum;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=m; j>=i; j--){
            val[i][j] += val[i][j+1];
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=i; j>=1; j--){
            cost[j][i] = cost[j+1][i] + val[j][i];
        }
    }
    
    for(int i=1; i<=m; i++) f[1][i] = cost[1][i];
    for(int i=2; i<=m; i++){
        dwuy(i, i, m, i-1, m);
    }
    for(int i=1; i<=m; i++){
        int ans = 0;
        for(int j=1; j<=m; j++) ans = max(ans, f[i][j]);
        cout << ans << '\n';
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 5 ms 14428 KB Output is correct
9 Correct 6 ms 16160 KB Output is correct
10 Correct 4 ms 14428 KB Output is correct
11 Correct 4 ms 14496 KB Output is correct
12 Correct 4 ms 14484 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 5 ms 14428 KB Output is correct
9 Correct 6 ms 16160 KB Output is correct
10 Correct 4 ms 14428 KB Output is correct
11 Correct 4 ms 14496 KB Output is correct
12 Correct 4 ms 14484 KB Output is correct
13 Correct 150 ms 90708 KB Output is correct
14 Correct 170 ms 93384 KB Output is correct
15 Correct 225 ms 168540 KB Output is correct
16 Correct 123 ms 92920 KB Output is correct
17 Correct 104 ms 92928 KB Output is correct
18 Correct 107 ms 92972 KB Output is correct