oj.uz

Submission #1033546

# Submission time Handle Problem Language Result Execution time Memory
1033546 2024-07-25T03:29:13 Z trMatherz Nafta (COI15_nafta) C++17
100 / 100
 349 ms 116164 KB 
#include <iostream>
 
 
// #include <fstream>
// std::ifstream cin ("cbarn.in");
// std::ofstream cout ("cbarn.out");
 
 
// includes
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
 
// usings
using namespace std;
using namespace __gnu_pbds;
 
// misc
#define ll long long
#define ld long double
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
typedef uint64_t hash_t;
 
// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()
#define vc vector<char>
#define vvc vector<vc>
 
// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second
 
// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T>
using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
// maps
#define mii map<int, int>
#define mll map<ll, ll>
 
// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for (auto &x : y)



int n, m; 
vs a;
vvl dp; 
vvl b; vvb v;
ll ct, lef, rig; 
void dfs(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= m || v[x][y] || a[x][y] == '.') return; 
    v[x][y] = true;
    ct += a[x][y] - '0'; emax(rig, y); emin(lef, y); 
    dfs(x + 1, y); 
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);   
}
void go(int l, int r, int rl, int rr, int k){
    int w = (l + r) / 2;
    ll bes = -1, p = -1; 
    for(int i = rl; i <= min(w, rr); i++){
        ll pop = dp[i][k - 1] + b[i + 1][w + 1]; 
        if(pop > bes) bes = pop, p = i; 
    }
    dp[w][k] = bes; 
    if(l != r) go(l, w, rl, p, k), go(w + 1, r, p, rr, k); 
}
int main(){
    cin >> n >> m; a = vs(n); A(u, a) cin >> u; 
    dp = vvl(m, vl(m)); b = vvl(m + 3, vl(m + 3, 0)); v = vvb(n, vb(m, false)); 
    F(i, n) F(j, m) 
        if(!v[i][j] && a[i][j] != '.') {
            ct = 0, lef = m + 5, rig = -5, dfs(i, j);
            b[0][lef + 1] += ct; b[lef + 1][lef + 1] -= ct; 
            b[0][rig + 2] -= ct, b[lef + 1][rig + 2] += ct; 
        }
    F(i, m) b[i + 1][0] += b[i][0], b[0][i + 1] += b[0][i]; 
    F(i, m) F(j, m) b[i + 1][j + 1] += b[i + 1][j] + b[i][j + 1] - b[i][j]; 
    F(i, m) dp[i][0] = b[0][i + 1]; 
    F(i, m - 1) go(0, m - 1, 0, m - 1, i + 1);
    F(i, m) {
        ll an = 0;
        F(j, m) emax(an, dp[j][i]);
        cout << an << endl;
    }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 2136 KB Output is correct
8 Correct 6 ms 2396 KB Output is correct
9 Correct 7 ms 2908 KB Output is correct
10 Correct 6 ms 2136 KB Output is correct
11 Correct 5 ms 2136 KB Output is correct
12 Correct 5 ms 2136 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 2136 KB Output is correct
8 Correct 6 ms 2396 KB Output is correct
9 Correct 7 ms 2908 KB Output is correct
10 Correct 6 ms 2136 KB Output is correct
11 Correct 5 ms 2136 KB Output is correct
12 Correct 5 ms 2136 KB Output is correct
13 Correct 287 ms 75344 KB Output is correct
14 Correct 314 ms 75424 KB Output is correct
15 Correct 349 ms 116164 KB Output is correct
16 Correct 249 ms 75376 KB Output is correct
17 Correct 272 ms 75348 KB Output is correct
18 Correct 261 ms 75348 KB Output is correct