oj.uz

Submission #535270

# Submission time Handle Problem Language Result Execution time Memory
535270 2022-03-09T20:53:13 Z Pichon5 Nafta (COI15_nafta) C++17
100 / 100
 417 ms 117900 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define ll long long
#define F first
#define S second
#define vll vector<long long>
#define int long long
using namespace std;
const int tam=2003;
vector<string>M;
int MI,MA,acum;
int r,s;
bool vis[tam][tam];
int Ini[tam][tam];
int sobra[tam][tam];//cantidad de petroleo si ya tome i y quiero tomar j. sobra[2002][j] si j es lo primero que tomo
int dp[tam][tam];//cuantos puse y cual fue el ultimo
//le tiro D&C pq transition_dp[k][i]>transition_dp[k][i+1]
bool check(int x, int y){
    if(vis[x][y]==true or x<0 or y<0 or x>=r or y>=s or M[x][y]=='.')return false;
    vis[x][y]=true;
    MI=min(y,MI);MA=max(MA,y);
    acum+=M[x][y]-'0';
    return true;
}

void dfs(int x, int y){
    if(!check(x,y))return;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
}

void solve(int g,int b, int e, int izq, int der){
    if(b>e)return;
    int mid=(b+e)/2;
    int k=0;
    dp[g][mid]=-1e9;
    for(int i=izq;i<=min(mid-1,der);i++){
        int niu=dp[g-1][i]+sobra[i][mid];
        if(niu>dp[g][mid]){
            k=i;
            dp[g][mid]=niu;
        }
    }
    solve(g,b,mid-1,izq,k);
    solve(g,mid+1,e,k,der);
}
signed main(){
    cin>>r>>s;
    string aux;
    for(int i=0;i<r;i++){
        cin>>aux;
        M.pb(aux);
    }
    int n=r,m=s;
    for(int i=0;i<n;i++){
        for(int l=0;l<m;l++){
            if(vis[i][l] or M[i][l]=='.')continue;
            MI=1e9,MA=-1,acum=0;
            dfs(i,l);
            Ini[MI][MI]+=acum; Ini[MI][MA+1]-=acum;
        }
    }
    for(int i=0;i<n;i++){
        int sum=0;
        for(int l=0;l<m;l++){
            sum+=Ini[i][l];
            Ini[i][l]=sum;
        }
    }
    for(int i=0;i<m;i++){
        int sum=0;
        for(int j=i-1;j>=0;j--){
            //muevo la parte de abajo que sería la que ya tomé
            sum+=Ini[j+1][i];
            sobra[j][i]=sum;
        }
        sum+=Ini[0][i];
        sobra[2002][i]=sum;
    }
    //calculo tomando 
    for(int i=0;i<m;i++)dp[1][i]=sobra[2002][i];
    for(int i=2;i<=m;i++){
        solve(i,0,m-1,0,m-1);
    }
    for(int i=1;i<=m;i++){
        int res=-1;
        for(int l=0;l<m;l++){
            res=max(res,dp[i][l]);
        }
        cout<<res<<"\n"; 
    }
    
    
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 7 ms 6468 KB Output is correct
8 Correct 9 ms 6396 KB Output is correct
9 Correct 11 ms 6932 KB Output is correct
10 Correct 10 ms 6472 KB Output is correct
11 Correct 8 ms 6400 KB Output is correct
12 Correct 8 ms 6448 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 7 ms 6468 KB Output is correct
8 Correct 9 ms 6396 KB Output is correct
9 Correct 11 ms 6932 KB Output is correct
10 Correct 10 ms 6472 KB Output is correct
11 Correct 8 ms 6400 KB Output is correct
12 Correct 8 ms 6448 KB Output is correct
13 Correct 324 ms 97440 KB Output is correct
14 Correct 409 ms 97552 KB Output is correct
15 Correct 417 ms 117900 KB Output is correct
16 Correct 327 ms 97612 KB Output is correct
17 Correct 333 ms 97532 KB Output is correct
18 Correct 320 ms 97448 KB Output is correct