Submission #281637

#	Time	Username	Problem	Language	Result	Execution time	Memory
281637		Mercenary	Nafta (COI15_nafta)	C++14	100 / 100	328 ms	85368 KiB

nafta

#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 (stderr)

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