oj.uz

Submission #932990

# Submission time Handle Problem Language Result Execution time Memory
932990 2024-02-24T17:33:28 Z idiotcomputer Nafta (COI15_nafta) C++11
100 / 100
 287 ms 70384 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second
#define pb push_back
 
const int mxN = 4*1e6;
const int mxS = 2000;
int R,S;
int sums[mxN];
pii bounds[mxN];
int grid[mxN];
int vis[mxN];

int cnt = 0;
void bfs(int node){
    queue<int> queue;
    queue.push(node);
    int curr,r,s;
    bounds[cnt].f = mxS+1;
    bounds[cnt].s = -1;
    while (queue.size() > 0){
        curr = queue.front();
        queue.pop();
        if (vis[curr] != -1 || grid[curr] == -1){
            continue;
        }
        vis[curr] = cnt;
        sums[cnt] += grid[curr];
        r = curr / S;
        s = curr % S;
        bounds[cnt].f = min(bounds[cnt].f, s);
        bounds[cnt].s = max(bounds[cnt].s, s);
        if (r > 0){
            queue.push(curr - S);  
        } 
        if (r < R-1){
            queue.push(curr+S);
        }
        if (s > 0){
            queue.push(curr-1);
        }
        if (s < S-1){
            queue.push(curr+1);
        }
    }
    cnt++;
}

int res[mxS+1];
int tres[mxS+1];
vector<vector<int>> cont(mxS+1);
vector<vector<int>> psums(mxS+1);
int added[mxS+1][mxS+1];

void dcdp(int l, int r, int sl, int sr){
    int m = (l+r)/2;
    tres[m] = 0;
    int bidx = -1;
   /* int cidx = 0;
    if (cont[m].size() > 0){
        cidx = lower_bound(cont[m].begin(),cont[m].end(),min(m-1,sr)) - cont[m].begin();
    }*/
    int cadd = 0;
    for (int i = m-1; i >= sl; i--){
       /* if (cont[m].size() > 0){
            while (cidx > 0 && cont[m][cidx-1] >= i){
                cidx--;
            }
        }*/
        cadd += added[m][i];
        if (res[i] + cadd > tres[m]){
            tres[m] = res[i] + cadd;
            bidx = i;
        }
    }
 //   cout << bidx << "\n";
    if (l != m){
        dcdp(l,m-1,sl,bidx);        
    } 
    if (r != m){
        dcdp(m+1,r,bidx,sr);
    }
} 
 
int main()
{
    memset(sums,0,sizeof(sums));
    
    for (int i =0; i < mxN; i++){
        vis[i] = -1;
    }
    
   // ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    
    cin >> R >> S; 
    
    string row;
    for (int i =0; i < R; i++){
        cin >> row;
        for (int j =0; j < S; j++){
            if (row[j] == '.'){
                grid[i*S+j] = -1;
            } else {
                grid[i*S+j] = row[j]-'0';
            }
        }    
    }
    for (int i = 0; i < R*S; i++){
        if (vis[i] == -1 && grid[i] != -1){
            bfs(i);
        }
    }

    memset(added,0,sizeof(added));    
    for (int i =0; i < cnt; i++){
        bounds[i].f += 1;
        bounds[i].s += 1;
        for (int j = bounds[i].f; j <= bounds[i].s; j++){
            if (added[j][bounds[i].f-1] == 0){
                cont[j].pb(bounds[i].f-1);
            }
            added[j][bounds[i].f-1] += sums[i];
        }
    }
    for (int i = 0; i <= S; i++){
        if (cont[i].size() == 0){
            psums[i].pb(0);
            continue;
        }
        sort(cont[i].begin(),cont[i].end());
        psums[i].resize(cont[i].size());
        psums[i][cont[i].size()-1] = added[i][cont[i][cont[i].size()-1]];
        for (int j = cont[i].size()-2; j >= 0; j--){
            psums[i][j] = added[i][cont[i][j]] + psums[i][j+1];
        }
        psums[i].pb(0);
    }
   
    memset(res,0,sizeof(res));
    int tot;/*
    cout << "RD\n";
    for (int i = 0; i <= S; i++){
        cout << cont[i].size() << ": ";
        for (int next : cont[i]){
            cout << next << ' ';
        }
        cout << '\n';
        for (int next : psums[i]){
            cout << next << " ";
        }
        cout << '\n';
    }*/
    for (int i = 0; i < S; i++){
        dcdp(0,S,0,S);
        tot = 0;
        for (int j = 0; j <= S; j++){
           /// cout << tres[j] << " ";
            tot = max(tot,tres[j]);
        }
    //    cout << '\n';
        cout << tot << '\n';
        swap(tres,res);
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 51388 KB Output is correct
2 Correct 9 ms 51292 KB Output is correct
3 Correct 7 ms 51196 KB Output is correct
4 Correct 8 ms 51248 KB Output is correct
5 Correct 8 ms 51292 KB Output is correct
6 Correct 8 ms 51292 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 51388 KB Output is correct
2 Correct 9 ms 51292 KB Output is correct
3 Correct 7 ms 51196 KB Output is correct
4 Correct 8 ms 51248 KB Output is correct
5 Correct 8 ms 51292 KB Output is correct
6 Correct 8 ms 51292 KB Output is correct
7 Correct 12 ms 51292 KB Output is correct
8 Correct 14 ms 51292 KB Output is correct
9 Correct 13 ms 51292 KB Output is correct
10 Correct 12 ms 51288 KB Output is correct
11 Correct 11 ms 51292 KB Output is correct
12 Correct 10 ms 51396 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 51388 KB Output is correct
2 Correct 9 ms 51292 KB Output is correct
3 Correct 7 ms 51196 KB Output is correct
4 Correct 8 ms 51248 KB Output is correct
5 Correct 8 ms 51292 KB Output is correct
6 Correct 8 ms 51292 KB Output is correct
7 Correct 12 ms 51292 KB Output is correct
8 Correct 14 ms 51292 KB Output is correct
9 Correct 13 ms 51292 KB Output is correct
10 Correct 12 ms 51288 KB Output is correct
11 Correct 11 ms 51292 KB Output is correct
12 Correct 10 ms 51396 KB Output is correct
13 Correct 195 ms 68072 KB Output is correct
14 Correct 281 ms 70384 KB Output is correct
15 Correct 287 ms 67664 KB Output is correct
16 Correct 176 ms 69968 KB Output is correct
17 Correct 155 ms 68996 KB Output is correct
18 Correct 132 ms 68848 KB Output is correct