Submission #1370346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370346		solution6312	Lawn Mower (CEOI25_lawnmower)	C++17	9 / 100	2097 ms	2792 KiB

lawn

#include "lawn.h"
#include <iostream>
using namespace std;
using ll=long long;

namespace
{
    const int MN=2e5+13;
    const ll inf64=1e18;
    int N; ll C, B;
    ll A[MN], V[MN];
    ll dp[MN];
    ll f(int L, int R)
    {
        ll ans=0;
        int cur=0;
        for (int i=L; i<=R; i++)
        {
            if (cur+V[i]>C)
            {
                ans+=A[i];
                ans+=B;
                ll cnt=(V[i]-C+cur)/C;
                if ((V[i]-C+cur)%C)
                {
                    ans+=(cnt+1)*A[i]+cnt*B;
                    cur=(V[i]-C+cur)%C;
                }
                else
                {
                    ans+=cnt*A[i]+cnt*B;
                    cur=0;
                }
            }
            else
            {
                ans+=A[i];
                cur+=V[i];
            }
            //cerr<<i<<": "<<ans<<' '<<cur<<endl;
        }
        if (cur) ans+=B;
        return ans;
    }
}

ll mow(int n, int c, int b, vector<int> &a, vector<int> &v)
{
    N=n; C=c; B=b;
    for (int i=1; i<=N; i++) A[i]=a[i-1];
    for (int i=1; i<=N; i++) V[i]=v[i-1];
    dp[0]=0;
    for (int i=1; i<=N; i++)
    {
        dp[i]=inf64;
        for (int j=0; j<i; j++)
        {
            dp[i]=min(dp[i], dp[j]+f(j+1, i));
        }
        //cerr<<i<<": "<<dp[i]<<endl;
    }
    return dp[N];
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 0 / 16
• Subtask 4: 0 / 36
• Subtask 5: 0 / 17
• Subtask 6: 0 / 22