oj.uz

Submission #281631

# Submission time Handle Problem Language Result Execution time Memory
281631 2020-08-23T09:25:09 Z Mercenary Nafta (COI15_nafta) C++14
11 / 100
 6 ms 3712 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] , r[maxn] , sum[maxn];
int a[maxn][maxn];
int b[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];
//    cout << sum[3] << endl;
    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:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
nafta.cpp: In function 'int main()':
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".INP", "r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:62:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   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 928 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct

Subtask #2
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 928 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Incorrect 6 ms 3712 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
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 928 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Incorrect 6 ms 3712 KB Output isn't correct
8 Halted 0 ms 0 KB -