oj.uz

Submission #281637

# Submission time Handle Problem Language Result Execution time Memory
281637 2020-08-23T09:28:09 Z Mercenary Nafta (COI15_nafta) C++14
100 / 100
 328 ms 85368 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e3 + 5;
const int logn = log2(maxn) + 1;

string s[maxn];
int dx[] = {-1 , 1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int nTime = 0;
int l[maxn * maxn] , r[maxn * maxn] , sum[maxn];
int a[maxn][maxn];
int n , m;

int dfs(int u , int v){
    int res = s[u][v] - '0';
    s[u][v] = '.';
    l[nTime] = min(l[nTime] , v + 1);
    r[nTime] = max(r[nTime] , v + 1);
    for(int i = 0 ; i < 4 ; ++i){
        if(u + dx[i] < 0 || u + dx[i] >= m || v + dy[i] < 0 || v + dy[i] >= n || s[u + dx[i]][v + dy[i]] == '.')continue;
        res += dfs(u + dx[i] , v + dy[i]);
    }
    return res;
}
int dp[maxn][maxn];

void solve(int k , int l , int r , int optl , int optr){
    if(l > r)return;
    int mid = l + r >> 1;
    int pos = mid;
    for(int i = optl ; i <= mid && i <= optr ; ++i){
        if(dp[k][mid] < dp[k - 1][i - 1] + sum[mid] + a[i - 1][mid]){
            dp[k][mid] = dp[k - 1][i - 1] + sum[mid] + a[i - 1][mid];
            pos = i;
        }
    }
    solve(k, l , mid - 1 , optl , pos);
    solve(k,mid + 1 , r , pos , optr);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> m >> n;
    for(int i = 0 ; i < m ; ++i)cin >> s[i];
    for(int i = 0 ; i < m ; ++i){
        for(int j = 0 ; j < n ; ++j)if(s[i][j] != '.'){
            l[nTime] = n;
            r[nTime] = 0;
            int res = dfs(i,j);
            for(int t = l[nTime] ; t <= r[nTime] ; ++t)sum[t] += res;
            a[l[nTime]][l[nTime]] -= res;
            a[r[nTime] + 1][r[nTime] + 1] -= res;
            a[l[nTime]][r[nTime] + 1] += res;
            a[r[nTime] + 1][l[nTime]] += res;
            ++nTime;
        }
    }
    for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= n ; ++j)a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    for(int i = 1 ; i <= n ; ++i){
        solve(i,1,n,1,n);
        int res = 0;
        for(int j = 1 ; j <= n ; ++j)res = max(res , dp[i][j]);
        cout << res << "\n";
    }
}

Compilation message

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
nafta.cpp: In function 'int main()':
nafta.cpp:60:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   freopen(taskname".INP", "r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:61:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   freopen(taskname".OUT", "w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 7 ms 3840 KB Output is correct
8 Correct 8 ms 3744 KB Output is correct
9 Correct 9 ms 4736 KB Output is correct
10 Correct 6 ms 3712 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 6 ms 3712 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 7 ms 3840 KB Output is correct
8 Correct 8 ms 3744 KB Output is correct
9 Correct 9 ms 4736 KB Output is correct
10 Correct 6 ms 3712 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 6 ms 3712 KB Output is correct
13 Correct 253 ms 44152 KB Output is correct
14 Correct 285 ms 41976 KB Output is correct
15 Correct 328 ms 85368 KB Output is correct
16 Correct 241 ms 41952 KB Output is correct
17 Correct 284 ms 40056 KB Output is correct
18 Correct 265 ms 40056 KB Output is correct