Submission #1095420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095420		rahidilbayramli	Maxcomp (info1cup18_maxcomp)	C++17	15 / 100	266 ms	596 KiB

maxcomp

#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//random_device rd;
//mt19937 gen(rd());
//uniform_int_distribution<> d(0, 1e9);
ll grid[25][25], vis[25][25];
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
ll cnt = 0;
void dfs(ll x, ll y, ll n, ll m)
{
    vis[x][y] = 1;
    cnt++;
    for(ll k = 0; k < 4; k++)
    {
        ll nx = x + dx[k], ny = y + dy[k];
        if(1 <= nx && nx <= n && 1 <= ny && ny <= m && !vis[nx][ny] && grid[nx][ny])
            dfs(nx, ny, n, m);
    }
}
void solve()
{
    ll n, m, i, j;
    cin >> n >> m;
    ll a[n+5][m+5];
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            cin >> a[i][j];
    }
    if(n * m <= 20)
    {
        ll res = 0;
        for(i = 1; i < (1 << (n * m)); i++)
        {
            vector<pll>vect;
            cnt = 0;
            ll maxx = LLONG_MIN, minn = LLONG_MAX;
            for(j = 0; j < n * m; j++)
            {
                ll x, y = (j + 1) % m;
                if(!y)
                    y = m;
                x = (j + 1 - y) / m + 1;
                grid[x][y] = 0;
                vis[x][y] = 0;
                if((i >> j) & 1){
                    minn = min(minn, a[x][y]);
                    maxx = max(maxx, a[x][y]);
                    vect.pb({x, y});
                    grid[x][y] = 1;
                }
            }
            dfs(vect[0].f, vect[0].s, n, m);
            ll sz = vect.size();
            if(cnt == sz)
                res = max(res, maxx - minn - sz);
        }
        cout << res << "\n";
    }
    else    if(n == 1)
    {
        ll res = -1;
        for(i = 1; i <= m; i++)
        {
            ll minn = a[1][i], maxx = a[1][i];
            for(j = i + 1; j <= m; j++)
            {
                minn = min(minn, a[1][j]);
                maxx = max(maxx, a[1][j]);
                res = max(res, maxx - minn - (j - i + 1));
            }
        }
        cout << res << "\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        solve();
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40