oj.uz

Submission #379319

# Submission time Handle Problem Language Result Execution time Memory
379319 2021-03-18T01:46:28 Z arwaeystoamneg Nafta (COI15_nafta) C++17
100 / 100
 564 ms 90092 KB 
/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//1000000007
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
/*
#ifndef arwaeystoamneg
#include ".h"
#endif*/
#ifdef arwaeystoamneg
#endif
int n, m, k;
vector<string>a;
vector<vi>visited, prefix;
void dfs(int i, int j)
{
	visited[i][j] = k;
	F0R(l, 4)
	{
		int x = i + dx[l], y = j + dy[l];
		if (x >= 0 && y >= 0 && x < n && y < m && a[x][y] != '.' && !visited[x][y])dfs(x, y);
	}
}
vi dp, ndp;
int get(int i, int j)
{
	return prefix[j][m] - prefix[j][i];
}
void solve(int l, int r, int tl, int tr)
{
	if (l > r)return;
	int mid = (l + r) / 2;
	pii best = { -inf,-1 };
	FOR(k, tl, min(mid, tr) + 1)
	{
		best = max(best, { dp[k] + get(k + 1,mid),k });
	}
	ndp[mid] = best.f;
	int x = best.s;
	solve(l, mid - 1, tl, x);
	solve(mid + 1, r, x, tr);
}
int main()
{
	setIO("");
	cin >> n >> m;
	a.rsz(n);
	F0R(i, n)cin >> a[i];
	visited.rsz(n, vi(m));
	k = 1;
	F0R(i, n)
	{
		F0R(j, m)
		{
			if (a[i][j] != '.' && !visited[i][j])
			{
				dfs(i, j);
				k++;
			}
		}
	}
	//pv(visited);
	vi val(k), left(k, m);
	F0R(i, n)F0R(j, m)
	{
		if (a[i][j] != '.')val[visited[i][j]] += a[i][j] - '0';
		left[visited[i][j]] = min(left[visited[i][j]], j);
	}
	//pv(val);
	//pv(left);
	prefix.rsz(m, vi(m + 1));
	F0R(j, m)
	{
		set<int>todo;
		F0R(i, n)
		{
			if (visited[i][j])
				todo.insert(visited[i][j]);
		}
		trav(x, todo)prefix[j][left[x]] += val[x];
		int sum = 0;
		F0R(i, m + 1)
		{
			sum += prefix[j][i];
			prefix[j][i] = sum - prefix[j][i];
		}
	}
	dp.rsz(m, -inf), ndp.rsz(m);
	F0R(i, m)dp[i] = get(0, i);
	cout << *max_element(all(dp)) << endl;
	FOR(i, 1, m)
	{
		fill(all(ndp), -inf);
		solve(0, m - 1, 0, m - 1);
		dp = ndp;
		cout << *max_element(all(dp)) << endl;
	}
}

Compilation message

nafta.cpp: In function 'void setIO(std::string)':
nafta.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:55:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 10 ms 1260 KB Output is correct
9 Correct 10 ms 2540 KB Output is correct
10 Correct 7 ms 1260 KB Output is correct
11 Correct 7 ms 1260 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 10 ms 1260 KB Output is correct
9 Correct 10 ms 2540 KB Output is correct
10 Correct 7 ms 1260 KB Output is correct
11 Correct 7 ms 1260 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct
13 Correct 532 ms 42368 KB Output is correct
14 Correct 564 ms 42220 KB Output is correct
15 Correct 534 ms 90092 KB Output is correct
16 Correct 484 ms 42220 KB Output is correct
17 Correct 413 ms 40300 KB Output is correct
18 Correct 420 ms 40300 KB Output is correct