Submission #485603

#	Time	Username	Problem	Language	Result	Execution time	Memory
485603		azberjibiou	도넛 (JOI14_ho_t3)	C++17	100 / 100	107 ms	3624 KiB

2014_ho_t3

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pss pair<short, short>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100005;
const int mxM=350;
const int mxK=350;
const ll MOD=998244353;
const ll INF=100000000000001;
int N;
ll A[mxN];
ll sum[mxN], cnt[mxN];
bool solv(ll num)
{
    for(int i=0;i<N;i++)    cnt[i]=sum[i]=0;
    while(sum[0]<num)
    {
        sum[0]+=A[cnt[0]];
        cnt[0]++;
    }
    for(int i=1;i<N;i++)
    {
        sum[i]=sum[i-1]-A[i-1];
        cnt[i]=cnt[i-1]-1;
        while(sum[i]<num)
        {
            sum[i]+=A[(i+cnt[i])%N];
            cnt[i]++;
        }
    }
    for(int i=0;i<N;i++)
    {
        int t1=i;
        int t2=(t1+cnt[t1])%N;
        int t3=(t2+cnt[t2])%N;
        int tsum=cnt[t1]+cnt[t2]+cnt[t3];
        if(tsum<=N) return true;
    }
    return false;
}
int main()
{
    gibon
    cin >> N;
    for(int i=0;i<N;i++)    cin >> A[i];
    ll s=INF, e=0;
    for(int i=0;i<N;i++)    s=min(s, A[i]);
    for(int i=0;i<N;i++)    e+=A[i];
    while(s!=e)
    {
        ll mid=(s+e)/2;
        if(solv(mid))   s=mid+1;
        else    e=mid;
    }
    cout << s-1;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50