Submission #561637

#	Time	Username	Problem	Language	Result	Execution time	Memory
561637		josanneo22	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	2 ms	468 KiB

sculpture

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
#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); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
/*
void duplicate(vi arr)
{
	arr.erase(unique(all(arr)),arr.end());
}
 
void file_in(string s)
{
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
boost::math::lcm(10,20) 
*/
/*CONVEX HULL
struct Point
{
    int x, y;
};
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}
vector<Point> hull;
void convexHull(Point points[], int n)
{
    if (n < 3) return;
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;
    int p = l, q;
    do
    {
        hull.push_back(points[p]);
        q = (p+1)%n;
        for (int i = 0; i < n; i++)
        {
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }
        p = q;
 
    } while (p != l); 
}
 
int main()
{
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
}
*/
/* RMQ with sparse
int lookup[MAX][MAX];
struct Query 
{
    int L, R;
};
 
void preprocess(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 0; (i + (1 << j) - 1) < n; i++)
        {
            if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                lookup[i][j] = lookup[i][j - 1];
            else
                lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
        }
    }
}
 
int query(int arr[], int L, int R)
{
    int j = (int)log2(R - L + 1);
    if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]])
        return arr[lookup[L][j]];
    else
        return arr[lookup[R - (1 << j) + 1][j]];
}
 
void RMQ(int arr[], int n, Query q[], int m)
{
    preprocess(arr, n);
    FOR(i,0,m)
    {
        int L = q[i].L, R = q[i].R;
        cout << query(arr, L, R) << endl;
    }
}
 
// Driver code
int main()
{
    int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    Query q[] = { { 0, 4 }, { 4, 7 }, { 7, 8 } };
    int m = sizeof(q) / sizeof(q[0]);
    RMQ(a, n, q, m);
    return 0;
}
*/
void normal()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
}
 
ll ex(int base, int power)
{
	if (power == 0)
		return 1;
	ll result = ex(base, power / 2);
	if (power % 2 == 1)
		return(((result * result) % mod) * base) % mod;
	else return (result * result) % mod;
}
int n,a,b;
const int maxn=2005;
ll dp[maxn];
ll ans=LLONG_MAX;
int solve(int se)
{
	vll v;
	for(int i=se;i<=n;i+=se)
	{
		if(i==se) v.pb(dp[i]);
		else v.pb(dp[i]-dp[i-se]);
	}
	ll temp=0;
	FOR(i,0,v.size())
	{
		temp|=v[i];
	}
	ans=min(ans,temp);
}
int main()
{
	normal();
	cin>>n>>a>>b;
	FOR(i,1,n+1)
	{
		int x;
		cin>>x;
		if(i==1) dp[i]=x;
		else dp[i]=dp[i-1]+x;
	}
	FOR(i,a,b+1)
		solve(i);
	cout<<ans;
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int solve(int)':
sculpture.cpp:15:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
sculpture.cpp:171:2: note: in expansion of macro 'FOR'
  171 |  FOR(i,0,v.size())
      |  ^~~
sculpture.cpp:176:1: warning: no return statement in function returning non-void [-Wreturn-type]
  176 | }
      | ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29