oj.uz

Submission #1095420

# Submission time Handle Problem Language Result Execution time Memory
1095420 2024-10-02T06:52:24 Z rahidilbayramli Maxcomp (info1cup18_maxcomp) C++17
15 / 100
 266 ms 596 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 348 KB Output is correct
2 Correct 260 ms 596 KB Output is correct
3 Incorrect 266 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 348 KB Output is correct
2 Correct 260 ms 596 KB Output is correct
3 Incorrect 266 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 348 KB Output is correct
2 Correct 260 ms 596 KB Output is correct
3 Incorrect 266 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -