oj.uz

Submission #530608

# Submission time Handle Problem Language Result Execution time Memory
530608 2022-02-26T02:46:46 Z Yuisuyuno Nafta (COI15_nafta) C++17
100 / 100
 407 ms 153688 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 2005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int m, n;
char a[N][N];
int vst[N][N];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
}

vector<ii> vec[N];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

bool ok(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

void dfs(int u, int v, int &l, int &r, int &dep){
    for(int i=0; i<4; i++){
        int x = u + dx[i];
        int y = v + dy[i];
        if (!ok(x,y) || a[x][y]=='.' || vst[x][y]) continue;
        vst[x][y] = 1;
        l = min(l,y);
        r = max(r,y);
        dep += a[x][y]-'0';
        dfs(x,y,l,r,dep);
    }
}

int g[N][N];
vector<vector<int>> f(2001,vector<int>(2001,0));

void solve(int cur, int l, int r, int otpl, int otpr){
    if (l > r) return;
    int mid = (l+r)>>1;
    ii Best = {minf,-1};
    for(int k=otpl; k<=min(mid,otpr); k++){
        Best = max(Best,{f[cur-1][k-1] + g[k][mid],k});
    }
    f[cur][mid] = Best.fi;
    solve(cur,l,mid-1,otpl,Best.se);
    solve(cur,mid+1,r,Best.se,otpr);
}

void proc(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if (a[i][j]!='.' && !vst[i][j]){
                vst[i][j] = 1;
                int l = j, r = j, dep = a[i][j]-'0';
                dfs(i,j,l,r,dep);
                vec[l].pb(ii(r,dep));
            }
        }
    }
    vector<int> cnt(m+2,0);
    for(int i=m; i>=1; i--){
        for(auto x : vec[i]){
            for(int j=i; j<=x.fi; j++) cnt[j]+=x.se;
        }
        for(int j=i; j<=m; j++) g[i][j] = cnt[j];
    }
    for(int i=1; i<=m; i++){
        solve(i,1,m,1,m);
        int ans = 0;
        for(int j=1; j<=m; j++) ans = max(ans,f[i][j]);
        cout << ans << '\n';
    }
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

nafta.cpp: In function 'void readfile()':
nafta.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32280 KB Output is correct
2 Correct 17 ms 32216 KB Output is correct
3 Correct 14 ms 32248 KB Output is correct
4 Correct 14 ms 32208 KB Output is correct
5 Correct 14 ms 32124 KB Output is correct
6 Correct 14 ms 32208 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32280 KB Output is correct
2 Correct 17 ms 32216 KB Output is correct
3 Correct 14 ms 32248 KB Output is correct
4 Correct 14 ms 32208 KB Output is correct
5 Correct 14 ms 32124 KB Output is correct
6 Correct 14 ms 32208 KB Output is correct
7 Correct 19 ms 36176 KB Output is correct
8 Correct 22 ms 36004 KB Output is correct
9 Correct 21 ms 37320 KB Output is correct
10 Correct 18 ms 35140 KB Output is correct
11 Correct 19 ms 35008 KB Output is correct
12 Correct 19 ms 34972 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32280 KB Output is correct
2 Correct 17 ms 32216 KB Output is correct
3 Correct 14 ms 32248 KB Output is correct
4 Correct 14 ms 32208 KB Output is correct
5 Correct 14 ms 32124 KB Output is correct
6 Correct 14 ms 32208 KB Output is correct
7 Correct 19 ms 36176 KB Output is correct
8 Correct 22 ms 36004 KB Output is correct
9 Correct 21 ms 37320 KB Output is correct
10 Correct 18 ms 35140 KB Output is correct
11 Correct 19 ms 35008 KB Output is correct
12 Correct 19 ms 34972 KB Output is correct
13 Correct 297 ms 107788 KB Output is correct
14 Correct 338 ms 101264 KB Output is correct
15 Correct 407 ms 153688 KB Output is correct
16 Correct 259 ms 88460 KB Output is correct
17 Correct 261 ms 82324 KB Output is correct
18 Correct 237 ms 82156 KB Output is correct