Submission #468884

#	Time	Username	Problem	Language	Result	Execution time	Memory
468884		MohammadParsaElahimanesh	Liteh and Newfiteh (INOI20_litehfiteh)	C++14	0 / 100	1 ms	332 KiB

Main

/// IN THE NAME OF GOD

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast","O3","unroll-loops")
//#pragma GGC target("avx2","fma")
//#pragma GCC optimize("no-stack-protector")

#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define RFOR(i,a,b) for(int i = b-1; i >= a; i--)
#define Fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	

typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;


int main()
{
	Fast
	
	int n;
	cin >> n;
	int l = log2(n)+1;
	int A[n];
	FOR(i,0,n)cin >> A[i];
	bool can[n][l];	
	FOR(i,0,n)FOR(j,0,l)can[i][j] = true;
	int ans = 0;
	FOR(i,0,n)
	{
		if(A[i])
		{
			RFOR(j,0,l)
			{
				bool ok = true;
				FOR(k,i,i+(1<<j))
				{
					if(k >= n || A[k] == 0)
					{
						ok = false;
						break;
					}
				}
				if(ok)
				{
					ans++;
					if(!can[i][j])ans++;
					FOR(k,i,i+(1<<j))A[k]--;
					
					FOR(k,i,i+(1<<j))
					{
						if(k-i-((k-i)&(i-k)) == 0)
						{
							FOR(t,0,log2(k-i-((k-i)&(i-k))))
							{
								can[k][t] = false;
							}
						}
						else
						{
							FOR(t,0,l)
							{
								can[k][t] = false;
							}
						}
					}
				}
				
			}
		}
	}
	
	FOR(i,0,n)if(A[i])
	{
		cout << -1;
		return 0;
	}
	cout << ans;
	return 0;
}

/// thank god

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70