oj.uz

Submission #1089091

# Submission time Handle Problem Language Result Execution time Memory
1089091 2024-09-16T03:21:57 Z nghiaaa Nafta (COI15_nafta) C++14
100 / 100
 204 ms 129784 KB 
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const int N = 2000 + 2;
int a[N][N];
int n, m, cost[N][N];
int dp[N][N];
struct DSU{
    int root, size, l, r, cost;
};
DSU dsu[N * N];
int h[N];
bool mark[N * N];
int getid(int x, int y)
{
    return (x - 1) * m + y;
}
int findset(int u)
{
    return u == dsu[u].root ? u : dsu[u].root = findset(dsu[u].root);
}
void Union(int u, int v)
{
    u = findset(u), v = findset(v);
    if (u == v) return ;
    if (dsu[u].size < dsu[v].size) swap(u, v);
    dsu[u].size += dsu[v].size;
    dsu[v].root = u;
    dsu[u].l = min(dsu[u].l, dsu[v].l);
    dsu[u].r = max(dsu[u].r, dsu[v].r);
    dsu[u].cost += dsu[v].cost;
}
void DAC(int l, int r, int L, int R, int c)
{
    int mid = (l + r) >> 1;
    int costbest = -1, savebest = -1;
    forw(i, L, min(mid, R))
    {
        int costi = cost[i][mid] + dp[i - 1][c - 1];
        if (costi > costbest)
            costbest = costi, savebest = i;
    }
    dp[mid][c] = costbest;
    if (l == r)
        return ;
    DAC(l, mid, L, savebest, c);
    DAC(mid + 1, r, savebest, R, c);
}
void solve()
{
    cin >> n >> m;
    forw(i, 1, n) forw(j, 1, m)
    {
        char val; cin >> val;
        a[i][j] = (val == '.' ? -1 : val - '0');
    }
    forw(i, 1, n) forw(j, 1, m)
    {
        if (a[i][j] < 0) continue;
        int r1 = getid(i, j);
        dsu[r1] = {r1, 1, j, j, a[i][j]};
        if (i > 1 && a[i - 1][j] >= 0)
            Union(r1, getid(i - 1, j));
        if (j > 1 && a[i][j - 1] >= 0)
            Union(r1, getid(i, j - 1));
    }
    forw(i, 1, n) forw(j, 1, m)
        if (a[i][j] >= 0 && !mark[findset(getid(i, j))])
        {
            int r1 = findset(getid(i, j));
            mark[r1] = 1;
            forw(z, dsu[r1].l, dsu[r1].r)
                cost[z][dsu[r1].r] += dsu[r1].cost;
        }
    forw(i, 1, m) forw(j, 1, i)
        cost[j][i] += cost[j][i - 1];
    forw(i, 1, m){
        DAC(i, m, i, m, i);
        cout << dp[m][i] << "\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    //time_t TIME_TU=clock();
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 5 ms 6576 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 4 ms 6236 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 5 ms 6748 KB Output is correct
9 Correct 5 ms 6576 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 4 ms 6236 KB Output is correct
13 Correct 187 ms 129616 KB Output is correct
14 Correct 204 ms 129784 KB Output is correct
15 Correct 194 ms 129620 KB Output is correct
16 Correct 139 ms 94544 KB Output is correct
17 Correct 146 ms 94544 KB Output is correct
18 Correct 142 ms 94544 KB Output is correct