Submission #535270

#	Time	Username	Problem	Language	Result	Execution time	Memory
535270		Pichon5	Nafta (COI15_nafta)	C++17	100 / 100	417 ms	117900 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66