oj.uz

Submission #1084383

# Submission time Handle Problem Language Result Execution time Memory
1084383 2024-09-06T07:19:03 Z vjudge1 Nafta (COI15_nafta) C++17
100 / 100
 312 ms 106440 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array

const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;

const int N = 3005;

int n, m;
string s[N];
int mx, mn, sum;
void dfs(int x,int y){
    if(x  < 0 || x >= n || y < 0 || y >= m || s[x][y] == '.')return;
    mn = min(mn, y);
    mx = max(mx, y);
    sum += s[x][y] - '0';
    s[x][y] = '.';
    dfs(x + 1, y);dfs(x - 1, y);
    dfs(x, y + 1);dfs(x, y - 1);
}

namespace fewwy{
    int bit[N];
    void upd(int i,int v){
        for(i++;i < N;i += i & -i)bit[i] += v;
    }

    int qry(int i){
        int ans = 0;
        for(i++;i;i -= i & -i)ans += bit[i];
        return ans;
    }

    int qry(int l,int r){
        return qry(r) - qry(l - 1);
    }
};
int C[N][N];
int dp[N][N];

void f(int l,int r,int tl,int tr,int j){
    if(l > r)return;
    int tm = (l+ r) / 2;
    int opt = tl;
    for(int i = tl;i <= min(tm, tr);i++){
        if(dp[i - 1][j - 1] + C[i][tm] > dp[tm][j]){
            dp[tm][j] = dp[i - 1][j - 1] + C[i][tm];
            opt = i;
        }
    }
    f(l, tm - 1, tl, opt, j);
    f(tm + 1, r, opt, tr, j);
}

bool comp(ar<int, 3> a, ar<int, 3> b ){
    return a[1] < b[1];
}

void skibidisigmaohiorizz(vector<ar<int, 3>> &e){
    sort(e.begin(), e.end(), comp);
    for(auto [l, r, v]: e)fewwy::upd(l, v);
    int k = 0;
    for(int j = 1;j <= m;j++){
        while(k < e.size() && e[k][1] < j){
            fewwy::upd(e[k][0], -e[k][2]);
            ++k;
        }
        for(int i = 1;i <= j;i++)C[i][j] = fewwy::qry(i, j);
    }
}

signed main() {
    cin>>n>>m;
    for(int i = 0;i < n;i++)cin>>s[i];
    vector<ar<int, 3> > e;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(s[i][j] == '.')continue;
            sum = 0, mx = j, mn = j;
            dfs(i, j);
            e.push_back({++mn, ++mx, sum});
        }
    }
    skibidisigmaohiorizz(e);
    for(int i = 1;i <= m;i++){
        f(1, m, 1, m, i);
        int mx = 0;
        for(int j = 1;j <= m;j++)mx = max(mx, dp[j][i]);
        cout<<mx<<'\n';
    }
}

Compilation message

nafta.cpp: In function 'void skibidisigmaohiorizz(std::vector<std::array<long long int, 3> >&)':
nafta.cpp:68:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(k < e.size() && e[k][1] < j){
      |               ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 7 ms 4544 KB Output is correct
8 Correct 7 ms 4384 KB Output is correct
9 Correct 6 ms 4956 KB Output is correct
10 Correct 6 ms 4384 KB Output is correct
11 Correct 5 ms 4264 KB Output is correct
12 Correct 6 ms 4188 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 7 ms 4544 KB Output is correct
8 Correct 7 ms 4384 KB Output is correct
9 Correct 6 ms 4956 KB Output is correct
10 Correct 6 ms 4384 KB Output is correct
11 Correct 5 ms 4264 KB Output is correct
12 Correct 6 ms 4188 KB Output is correct
13 Correct 312 ms 87208 KB Output is correct
14 Correct 298 ms 81320 KB Output is correct
15 Correct 301 ms 106440 KB Output is correct
16 Correct 299 ms 80824 KB Output is correct
17 Correct 250 ms 75344 KB Output is correct
18 Correct 279 ms 75348 KB Output is correct